Serialize and Deserialize Binary Tree
Understanding the Problem
We need to convert a binary tree into a string (serialize) and then reconstruct the exact same tree from that string (deserialize). The important word here is "exact." A tree with the same values is not enough; the structure has to match too. Left children must stay on the left, right children on the right, and null children must be preserved.
The difficulty comes from structure. Two different trees can produce the same inorder traversal of values, so a serialization that captures only values cannot tell them apart during deserialization. We need to encode the node values and where the nulls are, because null positions define the tree's shape.
Recording null markers (like "null" or "#") during traversal captures the complete structure. A preorder traversal with null markers uniquely defines a binary tree, and so does a level-order (BFS) traversal with null markers.
Key Constraints:
0 <= number of nodes <= 10^4: The tree can have up to 10,000 nodes. A skewed tree of this depth makes recursion depth a concern, which motivates the iterative BFS alternative.-1000 <= Node.val <= 1000: Node values can be negative. The parsing logic must treat a leading minus as part of the value, so "-1000" parses to the integer -1000 rather than a delimiter followed by "1000". Splitting on commas handles this, since the minus sign never appears as a delimiter.- The tree can be empty (0 nodes). Both serialize and deserialize must handle a null root.
Approach 1: DFS (Preorder Traversal)
Intuition
Preorder traversal (root, left, right) processes the root before either subtree. This ordering makes reconstruction direct: when we read the string back, the first token is always the current node, the tokens after it describe its left subtree, and whatever remains describes its right subtree.
Explicit null markers are what make this unambiguous. Without them, a node with only a left child and a node with only a right child would serialize identically. With them, the serialized string pins down both the values and the shape, so deserialization has exactly one valid interpretation.
The invariant that makes deserialization exact: a single recursive call consumes exactly the tokens that belong to its own subtree, no more and no fewer. A null marker is one token and one subtree (an empty one). A value token is followed by its full left subtree, then its full right subtree, both consumed by recursive calls before the call returns. Because every call leaves the index pointing at the first token of the next sibling subtree, the left call finishes precisely where the right call should begin.
Algorithm
Serialize:
- If the current node is null, append "N" to the result and return.
- Append the node's value to the result.
- Recursively serialize the left subtree.
- Recursively serialize the right subtree.
- Join all values with commas to form the final string.
Deserialize:
- Split the serialized string by commas into a list of tokens.
- Maintain an index (or use a queue/iterator) to track which token to process next.
- Read the next token. If it is "N", return null.
- Create a new tree node with the token's integer value.
- Recursively build the left child (this advances the index through the left subtree's tokens).
- Recursively build the right child (this advances the index through the right subtree's tokens).
- Return the constructed node.
Example Walkthrough
Code
- Time Complexity: O(n). Serialization visits every node exactly once. Deserialization processes every token exactly once. With n nodes, there are about 2n+1 tokens total, which is O(n).
- Space Complexity: O(n). The serialized string stores 2n+1 tokens. The recursion stack can go up to O(n) deep in the worst case (a completely skewed tree).
The DFS approach is O(n) in both time and space, which is optimal. Its one practical weakness is recursion depth: a skewed tree with 10,000 nodes causes 10,000 nested calls, which can overflow the call stack in languages with a small default stack. The next approach replaces the call stack with an explicit queue and serializes level by level instead of depth-first.
Approach 2: BFS (Level-Order Traversal)
Intuition
Instead of traversing depth-first, we serialize the tree level by level using BFS. This is the format LeetCode itself uses to represent binary trees in its input: [1,2,3,null,null,4,5].
A queue drives a level-by-level visit. For each node we dequeue, we append its value and enqueue both children. If a child is null, we append a null marker but enqueue nothing for it, since a null node has no children to expand.
Deserialization reverses this. The first token becomes the root and goes into a queue. For each node we dequeue, the next two tokens are its left and right children. A token of "N" means a null child; any other token becomes a new node that is attached and enqueued so its own children get assigned on a later iteration.
Because the work is driven by a queue rather than recursion, this version uses no call stack and handles deep trees without risk of stack overflow.
Serialize and deserialize agree because they enqueue nodes in the same order. During serialization, every non-null node appends exactly two tokens to the output (its left child and its right child). During deserialization, every non-null node we dequeue consumes exactly two tokens (its left child and its right child). Since both processes visit nodes in the same level-order sequence, the k-th non-null node produced during deserialization reads the same token pair that the k-th non-null node wrote during serialization. Null markers occupy a token but are never enqueued, so they never claim a child pair.
Algorithm
Serialize:
- If root is null, return an empty string.
- Initialize a queue with the root node.
- While the queue is not empty, dequeue a node.
- If the node is null, append "N" to the result.
- If the node is not null, append its value and enqueue its left and right children (even if they're null).
- Join all values with commas.
Deserialize:
- If the string is empty, return null.
- Split the string by commas into tokens.
- Create the root from the first token and add it to a queue.
- Starting from the second token, process tokens in pairs (left child, right child) for each node dequeued.
- For each token: if "N", set child to null. Otherwise, create a node, set it as child, and enqueue it.
- Return the root.
Example Walkthrough
Code
- Time Complexity: O(n). Both serialization and deserialization visit each node exactly once. Splitting the string and parsing integers are all O(n) operations overall.
- Space Complexity: O(n). The serialized string stores O(n) tokens. The BFS queue holds at most O(n) nodes (in the worst case, the widest level of a complete binary tree is about n/2 nodes).