LeetCode 297 · Trees

Serialize and Deserialize Binary Tree, explained with a picture

Packing a tree into a parcel tape and unpacking it.

HardTrees
▶ Watch it step by step

The problem

Design serialize (turn a binary tree into a string) and deserialize (turn that string back into the same tree).

Input:  [1, 2, 3, null, null, 4, 5]
Serialized: "1,2,#,#,3,4,#,#,5,#,#"
Output: the same tree, rebuilt

Picture it

Picture packing a tree into a parcel tape. Walk it in preorder (node, left, right) and write each value onto the tape. Whenever there is an empty spot, write #, so the shape travels too. To unpack, read the tape from the start: a value creates a node and then builds its left and right from the following tokens; a # means “nothing here”.

How to recognise it

  • You must turn a tree into flat text and back again, with nothing lost: same values, same shape.
  • A traversal alone loses the shape (different trees share a preorder), so the text must also record where the empty spots are.
  • With empty spots marked, one preorder list (node, left, right) is enough: reading it back is the same recursion in reverse.
  • Up to 10^4 nodes, values from −1000 to 1000, so negative numbers must survive the round trip.

Start with brute force

Store the tree like a heap array: the root at position 0 and the children of position i at 2i + 1 and 2i + 2. Write # for every unused position up to the last node.

def serialize_brute(root):
    slots = {}
    def place(node, i):              # heap positions: children of i are 2i+1, 2i+2
        if node:
            slots[i] = node.val
            place(node.left, 2 * i + 1)
            place(node.right, 2 * i + 2)
    place(root, 0)
    size = max(slots, default=-1) + 1
    return ",".join(str(slots[i]) if i in slots else "#" for i in range(size))

This is simple, and reading it back only needs the same position arithmetic. But the length depends on the height, not the number of nodes: a right-leaning chain of n nodes needs 2^n − 1 slots. With 20 nodes that is already about 10^6 slots; with 10^4 nodes it is impossible.

From brute force to the idea

  1. Find the waste. Heap positions reserve space for every missing descendant of a missing node, which explodes for deep trees.
  2. Mark only the empty spots you meet. Walk the tree in preorder. Write each value, and write one # for each empty child. Below a # nothing is written, so the output has n values and n + 1 markers.
  3. Read it back the same way. deserialize takes tokens from one shared iterator. make() reads a token: # means an empty spot; otherwise it creates the node, then builds the left subtree, then the right, exactly the order they were written.
  4. Separate tokens. Commas keep multi-digit and negative values like -1 and 10 apart, and int(t) turns them back into numbers.

This is the key idea: preorder with an explicit marker for every empty child records the shape exactly, and a recursive reader consumes the tokens in the same order.

A level-order version with # markers (LeetCode's own format) also works; both are O(n).

The key idea

Preorder with null markers makes the encoding unambiguous; decoding reads the tokens back in the same order. O(n).

Python solution

def serialize(root):
    out = []
    def walk(n):
        if not n:
            out.append("#"); return    # mark empty spots
        out.append(str(n.val)); walk(n.left); walk(n.right)
    walk(root)
    return ",".join(out)

def deserialize(data):
    tokens = iter(data.split(","))
    def make():
        t = next(tokens)
        if t == "#": return None
        n = Node(int(t)); n.left = make(); n.right = make()
        return n
    return make()

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute force (heap positions)O(2^h) in the worst case: one slot per position up to the deepest nodeO(2^h): the string itself
Preorder with markers (shown code)O(n): each node and each empty child written and read onceO(n): the string has 2n + 1 tokens, plus O(h) recursion

Edge cases

  • Empty tree: serialises to "#", which deserialises to None.
  • Single node: "1,#,#".
  • Negative values: [-1, 10] becomes "-1,10,#,#,#" and comes back unchanged.
  • Example tree [1, 2, 3, null, null, 4, 5]: "1,2,#,#,3,4,#,#,5,#,#".
  • Very deep tree: serialize recurses once per level, so a chain of about 1,000 nodes exceeds Python's default recursion limit, and LeetCode allows 10^4 nodes. deserialize also recurses per level. An explicit stack or a level-order (BFS) version avoids this.
  • The page leaves out the Node class (the usual val, left, right).

Common mistakes

  • Leaving out the empty markers, so [1, 2] and [1, null, 2] produce the same text.
  • Joining values without separators: 1 then 23 and 12 then 3 both give "123".
  • Rebuilding with a fresh index in each call instead of one shared position, so the same token is read twice.
  • Building the right child before the left while reading in preorder.
Your turn: serialise a BST compactly

If the tree is a binary search tree (BST: smaller left, bigger right, unique values), the empty markers can be dropped (LeetCode 449). Write serialize and deserialize that store only the values. Describe your approach, then write it if you like.

Compare with our answer

Write the plain preorder. When reading back, the BST order says where a value belongs: carry bounds (lo, hi) down, and a value outside the bounds cannot be in this subtree, so this spot is empty.

from math import inf

def ser_bst(root):
    out = []
    def walk(n):
        if n:
            out.append(str(n.val))
            walk(n.left)
            walk(n.right)
    walk(root)
    return ",".join(out)

def des_bst(data):
    vals = [int(t) for t in data.split(",")] if data else []
    i = 0
    def make(lo, hi):
        nonlocal i
        if i == len(vals) or not (lo < vals[i] < hi):
            return None
        node = Node(vals[i])
        i += 1
        node.left = make(lo, node.val)
        node.right = make(node.val, hi)
        return node
    return make(-inf, inf)

Both are O(n) time. The empty tree serialises to "".

A strong answer mentions: why the BST order replaces the markers, passing bounds down while reading, and one shared position in the token list.

Check what stuck

1. You must save a file-system tree (folders with any number of children) to text and restore it exactly. Which approach fits best?

2. Why is the shown format O(n) in size, unlike heap positions?

3. A learner drops the # markers and writes plain preorder values. Which pair of different trees now gives the same text?

Score 60% or more and the lesson is marked complete.