Serialize and Deserialize Binary Tree

Serialize and Deserialize Binary Tree asks you to turn a tree into a string and back again with no loss. It is a favorite interview question because the trick — record the nulls — is small but easy to miss, and it tests whether you really understand a preorder traversal.

The slow way first

A first instinct is to store just the values in some order, like a plain inorder list 2 1 4 3 5. But that fails: many different trees produce the same list of values, so you cannot tell which tree to rebuild. The structure — which child is missing — is lost.

The question to ask: what extra information do I need so the string is unambiguous? The answer is the null children. If the string also records every missing child, exactly one tree matches it.

The idea: preorder, and write "N" for null

Do a preorder walk (node, then left, then right). Append each node's value to the output. When the walk reaches a null child, append a sentinel "N" instead of skipping it. Those N markers pin down the shape.

To rebuild, read the tokens left to right with a single cursor. The first token is the root; a number means make a node and then build its left and right from the following tokens; an "N" means that child is null. Because we read in the same preorder we wrote, the cursor always lands on the right token.

The key insight: a preorder list with the nulls written in has exactly one matching tree, so the round trip is lossless.

Walk through it

Step through the animation. First serialize fills the token strip: each node writes its value, each null writes an "N". Then deserialize runs the cursor back across those same tokens, building one node per number and stopping a branch on each "N". The rebuilt tree on the left ends up identical to the one we started with.

Pseudocode

serialize(root):
    out = empty list
    walk(node):
        if node is null:
            append "N" to out          # record the missing child
            return
        append node.value to out
        walk(node.left)                # preorder: left, then right
        walk(node.right)
    walk(root)
    return out joined by spaces
 
deserialize(data):
    tokens = a left-to-right cursor over the split string
    build():
        tok = next token
        if tok == "N": return null
        node = new node with value tok
        node.left  = build()           # same preorder order
        node.right = build()
        return node
    return build()

The Python solution

def serialize(root):
    out = []
    def walk(node):
        if node is None:
            out.append("N")
            return
        out.append(str(node.val))
        walk(node.left)
        walk(node.right)
    walk(root)
    return " ".join(out)
 
def deserialize(data):
    tokens = iter(data.split())
    def build():
        tok = next(tokens)
        if tok == "N":
            return None
        node = TreeNode(int(tok))
        node.left = build()
        node.right = build()
        return node
    return build()

• walk is the preorder traversal. A null node appends "N" and returns — that sentinel is the whole trick.
• A real node appends its value, then recurses left then right, in that fixed order.
• " ".join(out) flattens the list into one space-separated string.
• iter(data.split()) makes a one-way cursor; next(tokens) hands back the next token each call.
• build mirrors walk exactly: read a token, return null on "N", else make a node and fill left then right. Reading in the same preorder is what keeps the cursor aligned.

Complexity

Both directions touch every node (and every null marker) a constant number of times, so both are linear. The string and the recursion stack are each O(n).

When this pattern shows up

Practice