Difficulty: HardTrees

Serialize and Deserialize Binary Tree

Problem in Plain English

Design a codec that converts any binary tree into a single string and rebuilds the exact original tree, including its shape, from that string. An empty tree must round-trip back to null.

Problem Statement

Implement serialize(root) to encode a binary tree as one string and deserialize(data) to rebuild the same values and left/right structure. The format is your choice; the array notation in the examples describes the tree, not a required serialized string.

An empty tree must round-trip to an empty tree. Assume the decoder receives strings produced by its matching encoder. The implementations below leave the input tree unchanged and allocate fresh nodes on every decode. Node values may repeat, so values cannot identify child positions.

Constraints

The tree contains between $0$ and $10^4$ nodes, inclusive.
Each node value is an integer in $[-1000,1000]$ .
No particular serialization format is required; each decoder must invert its matching encoder.

Examples

Example 1

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Node 1 has children 2 and 3; node 2 is a leaf; node 3 has children 4 and 5. Level order writes 1,2,3,N,N,4,5,N,N,N,N; preorder writes 1,2,N,N,3,4,N,N,5,N,N. Either matching decoder reconstructs the displayed tree, including both missing children of 2.

Example 2

Input: root = []
Output: []

Both encoders below write N for a missing root. The decoder reads that marker and returns null without allocating a node.

Example 3

Input: root = [0,null,-1000,0,1000]
Output: [0,null,-1000,0,1000]

The root has no left child and a right child valued -1000, whose children are 0 and 1000. Explicit markers preserve the asymmetric shape; commas keep the negative and multi-digit values separate; the repeated zero is another node, not a reference to the root.

Intuition

Values alone cannot describe a tree: a root with a left child and a root with a right child would otherwise look identical. Write a token for each value and a distinct N token for each absent child. In Example 1, the two absent children of 2 must appear before the children of 3 in level order, or immediately after 2 in preorder. A decoder following the same traversal can then put every value into exactly one child slot.

Approaches

Level Order Codec

Solution Details

Reveal Level Order Codec: intuition, complexity, and code

Intuition

Write every occupied or empty position in breadth-first order. On decode, a queue of real parents tells us whose left and right slots the next two tokens describe. For Example 1, the tokens after 1,2,3 are N,N for node 2, then 4,5 for node 3. Keep the trailing markers so every real parent always has exactly two child tokens.

Step-by-Step Logic

Begin Example 1 with queue [1] and an empty token list. Remove 1, write 1, and enqueue its left and right positions [2,3].
Remove 2, write 2, and append its two empty positions; remove 3, write 3, and append [4,5]. The queue is now [N,N,4,5].
Write the two N markers without adding children. Process 4 and 5, appending their four absent positions. Drain those markers and join the tokens as 1,2,3,N,N,4,5,N,N,N,N.
Decode the first token as a new root 1 with cursor i = 1. Its next two tokens create children 2 and 3; enqueue both and advance to i = 3.
Read N,N for parent 2, then 4,5 for parent 3. The real-parent queue becomes [4,5] and the cursor becomes i = 7.
Read N,N for each of 4 and 5; the queue is empty at i = 11. Return the new root describing [1,2,3,null,null,4,5].

Why It Works

The encoder starts with the root position. Whenever it writes a real node, it appends that node's left and right positions to a FIFO queue in that order; writing N appends nothing. Thus the first token identifies the root, and all later tokens come in left/right pairs for real parents in their queue order. The decoder starts with the same root and maintains that same ordered queue of real parents. For each parent, it consumes exactly its two child tokens: N leaves that slot empty, while a value allocates the child and appends it to the queue. Inductively, every processed parent has its original children and the remaining queue contains the corresponding unprocessed parents in the original order. When the queue empties, every edge and value is restored. All nodes are newly allocated, and serialization only reads the original links.

Dry Run

Level Order Codec: variable states at each step
Phase	Position or parent	Tokens written/read	Pending queue after	Decode cursor after
Encode	`1`	`1`	`[2,3]`	—
Encode	`2`	`2`	`[3,N,N]`	—
Encode	`3`	`3`	`[N,N,4,5]`	—
Encode	absent child of `2`	`N`	`[N,4,5]`	—
Encode	absent child of `2`	`N`	`[4,5]`	—
Encode	`4`	`4`	`[5,N,N]`	—
Encode	`5`	`5`	`[N,N,N,N]`	—
Encode	absent left child of `4`	`N`	`[N,N,N]`	—
Encode	absent right child of `4`	`N`	`[N,N]`	—
Encode	absent left child of `5`	`N`	`[N]`	—
Encode	absent right child of `5`	`N`	`[]`	—
Decode	root	`1`	`[1]`	`1`
Decode	`1`	`2,3`	`[2,3]`	`3`
Decode	`2`	`N,N`	`[3]`	`5`
Decode	`3`	`4,5`	`[4,5]`	`7`
Decode	`4`	`N,N`	`[5]`	`9`
Decode	`5`	`N,N`	`[]`	`11`; return `[1,2,3,null,null,4,5]`

Complexity Analysis

Time Complexity

O(n+1)

Space Complexity

O(n+1)

For n real nodes there are n+1 absent child positions, hence 2n+1 tokens even when n=0. Values have at most five characters under these constraints, so the encoded length is O(n+1). Each position is enqueued once and each real parent reads two tokens; final join and initial split each scan the string once. Java LinkedList and Python deque remove from the front in constant time. JavaScript advances a head index, avoiding shift; its array retains processed slots until the call ends. Tokens, encoded string and queues require O(n+1) storage; decoding also allocates n output nodes, with O(n+1) auxiliary storage even excluding them. No repeated concatenation or remaining-token slices are used.

Code

Solution.java

1import java.util.*;2
3class TreeNode {4    int val;5    TreeNode left, right;6    TreeNode(int val) { this.val = val; }7}8
9class Codec {10    public String serialize(TreeNode root) {11        List<String> tokens = new ArrayList<>();12        // LinkedList permits the null positions needed to preserve shape.13        Queue<TreeNode> queue = new LinkedList<>();14        queue.offer(root);15        while (!queue.isEmpty()) {16            TreeNode node = queue.poll();17            if (node == null) tokens.add("N");18            else {19                tokens.add(String.valueOf(node.val));20                queue.offer(node.left);21                queue.offer(node.right);22            }23        }24        return String.join(",", tokens);25    }26
27    public TreeNode deserialize(String data) {28        String[] tokens = data.split(",");29        if (tokens[0].equals("N")) return null;30        TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));31        Queue<TreeNode> queue = new ArrayDeque<>();32        queue.offer(root);33        int i = 1;34        while (!queue.isEmpty()) {35            TreeNode parent = queue.poll();36            // Every real parent owns exactly the next two child-position tokens.37            if (!tokens[i].equals("N")) {38                parent.left = new TreeNode(Integer.parseInt(tokens[i]));39                queue.offer(parent.left);40            }41            i++;42            if (!tokens[i].equals("N")) {43                parent.right = new TreeNode(Integer.parseInt(tokens[i]));44                queue.offer(parent.right);45            }46            i++;47        }48        return root;49    }50}

Hints

Hint 1

Distinguish a missing child from a node whose value is zero; a separate N marker carries shape.

Hint 2

Use a comma delimiter so negative and multi-digit integers can be read as complete tokens.

Hint 3

A breadth-first decoder consumes two tokens per real parent. A preorder decoder finishes a child subtree before resuming its parent.

Hint 4

For preorder without recursion, track each unfinished parent and its next child side; push right before left when encoding.

Edge Cases

An absent root encodes as N in both versions and decodes without allocating nodes.
A single node writes its value and two markers; repeated values must still allocate distinct node objects.
Left-only and right-only chains require markers on opposite sides. A 10,000-node chain must work without changing recursion limits.
Zero, -1000 and 1000 are valid values. Negative signs and multiple digits are preserved by comma-separated tokens.
Calling deserialize twice on the same string produces equal shapes with disjoint node identities; changing one result must not change the other or the original.

Common Mistakes and Interview Tips

Dropping null markers: [1,2] and [1,null,2] would become indistinguishable.
Treating a zero value as an absent node. Test the node reference, not its numeric value.
Using Java ArrayDeque to store null positions: it rejects null entries. The encoder below uses LinkedList for nullable positions.
Using JavaScript shift repeatedly, slicing the remaining tokens per subtree, or repeatedly concatenating growing immutable strings can introduce quadratic work.
Pushing left before right during iterative preorder reverses the intended order. A stack pops the last pushed item first.
Advancing an ancestor to its next child only after visiting a descendant misaligns tokens. Update or pop the parent frame before pushing a real child.
Keeping tokens or cursor fields across calls can leak state. Assuming recursion survives a maximum-depth chain can fail despite a correct recurrence.
Mixing codec formats: the breadth-first string and preorder string require their corresponding decoders; accepting malformed arbitrary strings is outside this contract.

Key Takeaway

Lossless tree encoding needs a traversal order plus explicit structure markers. Reconstruct with the same order and a queue of parents or stack of unfinished child slots. A linear traversal becomes a linear codec only when string building and token consumption also avoid repeated copying.