Serialize Deserialize Binary Tree LeetCode 297

LeetCode 297 — Serialize and Deserialize Binary Tree — asks you to design a Codec class with two methods: serialize(root) encodes a binary tree into a string, and deserialize(data) decodes the string back into the original tree.

The serialization format is your choice — there is no fixed format. The only requirement is that deserialize(serialize(root)) returns a tree identical to root. The tree may contain duplicate values, and nodes can have any integer value.

Two common approaches: preorder DFS with null markers (concise and recursive), and BFS level-order (iterative with a queue). Both encode the tree structure unambiguously and decode in O(n) time.

Serialize: traverse the tree in preorder (root, left, right). For each node, write its value. For each null child, write a sentinel like "N" or "null". Separate values with commas. The null markers preserve the tree structure.

For example, tree [1, 2, 3, null, null, 4, 5] serializes to "1,2,N,N,3,4,N,N,5,N,N". Each null marker tells the deserializer where subtrees end. Without null markers, preorder alone is ambiguous.

Deserialize: split the string by commas into tokens. Use a pointer (or iterator) to consume tokens left-to-right. Read the next token: if "N", return null. Otherwise, create a node with that value, recursively build its left subtree (consuming more tokens), then its right subtree.

Serialize: BFS with a queue. Start with root. For each node in the queue: if non-null, write its value and enqueue its left and right children (even if null). If null, write "N". This produces a level-order encoding.

Deserialize: split into tokens. Create the root from the first token. Use a queue. For each node in the queue, read two tokens (left child and right child). If non-null, create nodes and enqueue them. This mirrors the serialize order exactly.

The BFS approach is more intuitive for visual learners — the serialized string maps directly to the tree level by level. However, the DFS approach uses less code and is more common in interview solutions.

Consider tree: 1 (left: 2, right: 3 with left: 4, right: 5). Preorder serialize: visit 1 → "1", visit 2 → "2", left null → "N", right null → "N", visit 3 → "3", visit 4 → "4", left null → "N", right null → "N", visit 5 → "5", left null → "N", right null → "N". Result: "1,2,N,N,3,4,N,N,5,N,N".

Deserialize "1,2,N,N,3,4,N,N,5,N,N": read "1" → create node 1. Left: read "2" → create node 2. Left: read "N" → null. Right: read "N" → null. Back to 1. Right: read "3" → create node 3. Left: read "4" → node 4 (left N, right N). Right: read "5" → node 5 (left N, right N).

The token consumption is sequential — each recursive call consumes the next token. No backtracking or lookahead needed. The preorder structure naturally matches the recursive descent pattern.

Python DFS: def serialize(root): if not root: return "N". return str(root.val) + "," + serialize(root.left) + "," + serialize(root.right). def deserialize(data): tokens = iter(data.split(",")). def build(): val = next(tokens). if val == "N": return None. node = TreeNode(int(val)). node.left = build(). node.right = build(). return node. return build().

Java DFS: serialize uses StringBuilder with preorder. deserialize uses a Queue<String> of tokens. The build method polls the queue, checks for "N", and recursively constructs left and right children.

The Python version is remarkably clean — about 12 lines total for both methods. The iterator approach eliminates the need for an explicit index variable. Java requires slightly more boilerplate but follows the same logic.

Serialize: O(n) time — each node is visited exactly once. O(n) space for the output string (each node contributes its value and potentially "N" for null children). The recursion stack uses O(H) space where H is the tree height.

Deserialize: O(n) time — each token is consumed exactly once. O(n) space for the token array and the reconstructed tree. The recursion stack uses O(H) space.

Both operations are optimal — we must visit every node to encode the tree, and we must read every token to decode it. The null markers add at most n+1 extra tokens (a tree with n nodes has n+1 null pointers).

Serialize and Deserialize BST (LeetCode 449) is the BST version. Since BSTs have an ordering constraint, you can serialize without null markers — preorder alone is sufficient because the BST property determines the structure during deserialization.

Construct Binary Tree from Preorder and Inorder (LeetCode 105) reconstructs a tree from two traversals. Serialize/Deserialize uses one traversal plus null markers instead. Both test tree reconstruction skills from different angles.

Binary Tree Right Side View (LeetCode 199) and Kth Smallest in BST (LeetCode 230) use BFS and inorder traversals respectively. Together with serialization (preorder), these cover all major tree traversal applications.