Serialize and Deserialize Binary Tree
Problem
Design two functions: one that encodes a binary tree into a string, and one that decodes that string back into an identical tree. Any format is allowed as long as the round trip reproduces the original structure and values.
Examples
Constraints
- • 0 <= number of nodes <= 10^4
- • -1000 <= Node.val <= 1000
Hints & approach
Hint 1
A traversal alone is ambiguous, unless you also record where the null children are.
Hint 2
Preorder with an explicit marker for null uniquely describes a tree.
Hint 3
When decoding, consume tokens with a shared index and rebuild recursively in the same preorder.
Approachtry the hints first
Serialize with a preorder DFS, writing each value followed by a comma and writing a marker such as "#" for every null child. To deserialize, split the string into tokens and recurse with a moving index: read a token; if it is the null marker return null, otherwise create the node and build its left then right subtree from the following tokens. Because nulls are explicit, the encoding is unambiguous.
Time O(n) · Space O(n)