87. Serialize and Deserialize Binary Tree
Design an encoding and decoding pair that preserves the tree's full structure, including missing children. Decoding a valid encoding must reconstruct the corresponding node values and positions.
A list of values without shape information is insufficient. Follow the documented format and validation rules for malformed encodings.
Example 1
Input
tree=[1,2,3,null,4]
Output
1,2,#,4,#,#,3,#,#
Explanation: Null markers distinguish a missing left child from a missing right child.
Example 2
Input
tree=[]
Output
text=#; decoded root=null
Explanation: Null has one complete grammar token.
Example 3
Input
text=1,#
Output
IllegalArgumentException
Explanation: The root still needs its right-child token.
Constraints
0 <= node count per tree <= 105-231 <= node.value <= 231 - 1- Each input is a proper binary tree: no cycles or shared child nodes. Null trees are permitted.
Hints
Hint 1
How will you distinguish the two sides of a missing child?
Hint 2
A value token consumes one slot and creates two ordered child slots; # only consumes one.
Hint 3
Use a preorder wrapper stack to write and a left/right slot stack to read, then check exact completion.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Round trip with explicit missing child slots
[1,2,3,null,4]
{"serialized":"1,2,#,4,#,#,3,#,#","decoded":[1,2,3,null,4]}