Serialize Binary Tree LeetCode 297 Guide

LeetCode 297 Serialize and Deserialize Binary Tree asks you to design a Codec class with two methods: serialize(root) converts a binary tree to a string, and deserialize(data) converts that string back to the original binary tree. The key constraint is that the round trip must be lossless — deserializing the serialized output must produce a tree that is structurally and value-identical to the original.

This is an open-ended design problem: the format of the string is entirely up to you. There is no single correct encoding, but some encodings are much easier to implement than others. The challenge is choosing a format that uniquely identifies the tree structure — not just the values — so that deserialization can reconstruct the exact shape, including all null children.

The problem applies to any binary tree: balanced or skewed, complete or sparse, with duplicate values. You cannot assume any special structure that would simplify encoding. A robust solution must handle trees with a single node, completely left-skewed or right-skewed trees, and trees where many internal nodes have only one child.

Inorder traversal visits left subtree, then the current node, then right subtree. For a binary search tree, inorder produces a sorted sequence that uniquely defines the values — but not the shape. Many structurally different trees produce the same inorder sequence. For example, a root with value 2, left child 1, and right child 3 produces the same inorder as a root with value 1 and right child 2 that has a right child 3. Without knowing the root or the shape, you cannot reconstruct the tree from inorder alone.

Combining two traversals — such as preorder + inorder or postorder + inorder — does uniquely define a binary tree when all values are distinct. But this approach requires two passes and non-trivial reconstruction logic that is error-prone in an interview setting. It also fails when the tree contains duplicate values, making it unsuitable as a general-purpose codec.

The solution is to include structural information directly in the serialization. By recording null children as explicit markers, a single traversal — preorder or level-order — uniquely defines both the values and the shape. You no longer need a second traversal because the null markers tell you exactly where each subtree ends.

Preorder DFS visits a node before its children: first the node itself, then the left subtree, then the right subtree. To serialize a binary tree using preorder, you apply this traversal recursively. When you reach a non-null node, you emit its value. When you reach a null child, you emit a sentinel — typically the string "null" or the character "#". All emitted values are collected into a list and joined with commas to produce the final string.

The result is a flat, linear string that encodes both values and structure. For a tree with root 1, left child 2, and right child 3, the preorder with null markers produces "1,2,null,null,3,null,null". Every leaf is followed by two null markers for its absent left and right children. Every internal node with only one child has one null marker for the missing child. This encoding is unambiguous: there is exactly one tree that produces any given valid preorder string with null markers.

The serialization is a single DFS pass — O(n) time and O(n) space for the output list plus the recursion stack. The recursion depth is O(h) where h is the tree height, which is O(n) in the worst case for a skewed tree. The comma-separated format makes splitting trivial during deserialization.

To deserialize, split the string by comma to get a list of tokens. The key insight is that the tokens are in preorder, so you can reconstruct the tree by consuming tokens in order — the first token is the root, the next tokens recursively define the left subtree, and then the right subtree. The null markers tell you exactly when a subtree is empty and you should stop recursing.

The cleanest implementation uses an iterator or a deque over the token list. Each recursive call consumes exactly one token from the front of the iterator. If the token is "null", return None immediately (this subtree is empty). Otherwise, create a new TreeNode with the integer value of the token, then recursively assign its left child (consuming the next token) and its right child (consuming the token after that). Return the constructed node.

This iterator approach eliminates the need to pass an index by reference or return a (node, index) tuple. The iterator's internal pointer advances automatically with each next() call, making the recursive code as clean as the serialization code. The deserialization is also O(n) time and O(n) space for the recursion stack plus the token list.

An alternative to preorder DFS is BFS level-order serialization. You use a queue starting with the root. For each node dequeued, you emit its value (or "null" if it is None). For non-null nodes, you enqueue both children — even null ones — so that their positions are recorded in the output. This produces a level-by-level encoding similar to LeetCode's own tree representation format.

Level-order serialization naturally mirrors the way LeetCode displays trees in problem statements, which can make debugging easier. The tradeoff is that it tends to produce longer strings than preorder for sparse trees, because you must emit nulls for all missing children at every level until the last non-null node in the final level.

Deserialization from a BFS encoding also uses a queue. Read the first token as the root. Then use a queue of parent nodes. For each parent dequeued, read the next two tokens as its left and right children. If a token is "null", that child is null (and is not enqueued). If it is a value, create the child node and enqueue it for its own children to be assigned. Continue until all tokens are consumed.

Python preorder Codec: class Codec: def serialize(self, root): res=[]; def dfs(n): res.append(str(n.val) if n else "null"); n and (dfs(n.left) or dfs(n.right)); dfs(root); return ",".join(res). def deserialize(self, data): it=iter(data.split(",")); def dfs(): v=next(it); return None if v=="null" else TreeNode(int(v),dfs(),dfs()); return dfs(). The serialize and deserialize methods are each under 5 lines of meaningful code. Time and space are O(n) in both directions.

Java preorder Codec: public String serialize(TreeNode root){ StringBuilder sb=new StringBuilder(); dfs(root,sb); return sb.toString(); } void dfs(TreeNode n,StringBuilder sb){ if(n==null){sb.append("null,");return;} sb.append(n.val+","); dfs(n.left,sb); dfs(n.right,sb); } public TreeNode deserialize(String data){ Queue<String> q=new LinkedList<>(Arrays.asList(data.split(","))); return dfs(q); } TreeNode dfs(Queue<String> q){ String s=q.poll(); if(s.equals("null"))return null; TreeNode n=new TreeNode(Integer.parseInt(s)); n.left=dfs(q); n.right=dfs(q); return n; }

Both implementations follow the same structure. The preorder approach is shorter and more elegant than the BFS approach, especially in Python. The O(n) time and space guarantees hold for both the serialize and deserialize directions. The preorder codec also handles skewed trees naturally, while BFS may allocate a very wide queue for wide trees.

Construct Binary Tree from Preorder and Inorder Traversal (LeetCode 105) and from Postorder and Inorder (LeetCode 106) are classic reconstruction problems that do not use null markers. They require two traversal arrays and non-trivial boundary logic to split left and right subtrees. LeetCode 297 is simpler in practice because the null markers in the single preorder traversal make reconstruction unambiguous without needing a second array.

Binary Tree Level Order Traversal (LeetCode 102) and Flatten Binary Tree to Linked List (LeetCode 114) both involve traversing or restructuring binary trees. Flatten Binary Tree is particularly related: it rearranges the tree into a preorder linked list in-place, which is the structural equivalent of the preorder serialization — just stored as pointers rather than a string.

The tree serialization family extends to more complex structures. Serialize and Deserialize N-ary Tree (LeetCode 428) and Serialize and Deserialize BST (LeetCode 449) are follow-up problems. For a BST, you can omit null markers and use the BST property to reconstruct the tree from preorder alone — which is a useful optimization but only valid when the tree is guaranteed to be a BST. For a general binary tree, null markers are always required.