Serialize and Deserialize Binary Tree

Problem

Distributed caches ship binary trees between nodes as strings. Design two functions: serialize(root) encodes a tree to a comma-separated string, and deserialize(data) rebuilds the exact tree from it. The encoding must be self-delimiting - no external length or shape metadata - so the receiver can reconstruct any tree, including empty subtrees anywhere in the structure.

Example 1:

Input: root = [9,6,14,3,8,11,17,null,null,null,null,null,12]
serialize(root) -> "9,6,3,#,#,8,#,#,14,11,#,12,#,#,17,#,#"
Explanation: preorder tokens - each node's value followed by its full left then right subtree; '#' marks an absent child.

Example 2:

Input: root = []
serialize(root) -> "#"
Explanation: the empty tree is a single null marker.

Constraints:

• The number of nodes in the tree is in the range [0, 10^4].
• -1000 <= Node.val <= 1000
• The input tree is a plain binary tree, not necessarily balanced or sorted.

Tree:        9
           /   \
          6     14
         / \   /  \
        3   8 11  17
                \
                 12
 
tokens:  9,6,3,#,#,8,#,#,14,11,#,12,#,#,17,#,#
         ^ root first, then the entire left subtree (6...),
           then the entire right subtree (14...). Note the lone #
         after 11: its left child is absent, so the next token 12
         is 11's right child.

Solution Breakdown

Approach - preorder tokens with a null marker, decoded through one shared iterator.

Preorder writes the node's value, then the entire left subtree, then the entire right subtree. That alone is ambiguous - two different trees can share values - so every absent child is written as the reserved token #, including both children of every leaf. The result is self-delimiting: reading the stream back with the same rule tells you the first token is the root, the next run of tokens is consumed completely by the left subtree, and the right subtree takes the rest. No lengths, no shape bits, no recursion depth metadata - the token order is the structure.

The deserializer leans on a property that is easy to miss: each recursive call consumes exactly the tokens encoding its own subtree and leaves the stream positioned just past them. Threading one shared iterator through the recursion makes that bookkeeping implicit - build() reads a token; if it is # the subtree is absent (None), otherwise the token is a node value and two nested calls build its children from whatever the stream still holds. The alternative - passing an index around - must use mutable state (nonlocal or a one-element wrapper) because a plain integer index passed by value would lose the increments from child calls and re-read consumed tokens. Trace the example tree: 9,6,3,#,#,8,#,#,14,11,#,12,#,#,17,#,# - the lone # after 11 is what tells the reader that 12 is 11's right child, not its left. Round-tripping is verified structurally: deserialize the serialized string, walk both trees comparing values and shape, or simply re-serialize and diff the strings.

Edge cases - the empty tree is the single token #; a leaf emits value,#,#; a node with only a right child still marks the missing left child (11,#,12,...); negative and multi-digit values ride the comma delimiter untouched.

Complexity - O(n) time both directions: every node contributes one value token plus two markers on the way out, and every token is read exactly once on the way in. O(n) space for the token list and output string, O(h) recursion depth - O(n) worst case on a skewed tree, where a level-order (BFS) codec's explicit queue would be the flatter alternative.