Serialize and De-serialize BT
HardPreorder with explicit nulls
Problem
Serialize a binary tree to a string and deserialize it back to the same tree.
Write the tree with markers for nulls (e.g. preorder); reading it back reconstructs the same tree.
The idea
Write a preorder traversal that emits a marker for every null child; those markers are what make the string unambiguous without a second traversal. Deserialising reads the same sequence and rebuilds in exactly the same order.
The trick
- Null markers are mandatory — without them the shape is lost.
- Deserialise with a moving index over the tokens, in the same preorder.
- Level order with markers works equally well.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — [1,2,3,null,null,4,5] Values: 1, 2, 3, 4, 5.
1serialize: preorder/level-order with '#' for null2deserialize: read tokens, rebuild in the same orderInput
- array
- [1, 2, 3, 4, 5]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- tree = [1,2,3,null,null,4,5]
- Output:
- "1,2,3,#,#,4,5"
- Explanation:
- Flatten to a string, then rebuild it exactly.
Example 2
- Input:
- tree = [1]
- Output:
- "1"
- Explanation:
- One node.
Example 3
- Input:
- tree = []
- Output:
- "(empty)"
- Explanation:
- Empty tree serializes to nothing.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.