L3 · FAANGTrees~25 min · 5 tests

Serialize and Deserialize a Binary Tree

Encode a binary tree to a string and rebuild exactly the same tree using pre-order traversal with null markers, in O(n) each way. A classic FAANG hard.

The problem

Implement serialize(root) -> str and deserialize(data) -> TreeNode so that deserialize(serialize(t)) rebuilds exactly the same tree structure and values (values are integers, possibly negative).

TreeNode, build_tree and tree_values are provided.

Examples

Example 1

Input

roundtrip(serialize, deserialize, [1, 2, 3, None, None, 4, 5])

Expected output

[1, 2, 3, None, None, 4, 5]

Example 2
Input
```
roundtrip(serialize, deserialize, [])
```
Expected output
```
[]
```

+ 3 hidden tests on Submit — negatives and a right chain, equal values.

Edge cases to ask about

Empty tree
Negative values
Skewed tree

How the tests call your code

These helpers run before your code. The test inputs above call them.

from collections import deque as _deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build_tree(values):
    """Level-order list -> tree. None marks a missing child: [3, 9, 20, None, None, 15, 7]."""
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    queue, i = _deque([root]), 1
    while queue and i < len(values):
        node = queue.popleft()
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i]); queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i]); queue.append(node.right)
        i += 1
    return root


def tree_values(root):
    """Tree -> level-order list with trailing Nones trimmed (the inverse of build_tree)."""
    out, queue = [], _deque([root])
    while queue:
        node = queue.popleft()
        if node is None:
            out.append(None)
            continue
        out.append(node.val)
        queue.append(node.left)
        queue.append(node.right)
    while out and out[-1] is None:
        out.pop()
    return out


def roundtrip(serialize, deserialize, values):
    s = serialize(build_tree(values))
    if not isinstance(s, str):
        return "serialize must return a str"
    return tree_values(deserialize(s))

Hints

0/3

How an interviewer scores this

0/9

1. Understand the problemRestate it, ask about edge cases and input size.
2. Write a brute-force solutionCorrect first, clever later.
3. Get the correct outputautoAll visible examples pass.
4. Analyse time complexityautoCommit to a Big-O in the Complexity Lab.
5. Analyse space complexityautoExtra memory, not the input.
6. Identify the bottleneckautoMeasure your code — where does it bend?
7. OptimiseUsually: a set or dict instead of a scan.
8. Explain why it worksSay it out loud to Solvi.
9. Test the edge casesautoSubmit passes every hidden test.

Python 3.13 · serialize

def serialize(root):
    pass


def deserialize(data):
    pass

⌘/Ctrl + Enter runs the examples

Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.

Complexity Lab

What does this cost as n grows?

Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and read why.

Time complexity of the optimal solution

Space complexity (extra memory)

Pick both to reveal the answer.

From brute force to optimal

The progression an interviewer wants to hear, one step at a time.

Approach	Time	Space	Idea
Pre-order with null markers	O(n)	O(n)	Null markers make the structure unambiguous.
bestLevel-order (BFS)	O(n)	O(n)	The LeetCode display format.

Walkthrough of the optimal approach (try it yourself first)

Pre-order (node, left, right) with a marker for every missing child uniquely describes a tree. Deserialising reads tokens in the same order: a value creates a node and is then followed by its left subtree and right subtree; # means "no child here".

Both directions are iterative here, so a 10,000-node skewed tree doesn't hit the recursion limit. A recursive version with iter(tokens) and next() is shorter — fine to write if you mention the limit.

Complexity: O(n) time, O(n) space. Each node is written and read once; the string and the stack are O(n).

Reveal the reference solution

def serialize(root):
    out = []
    stack = [root]
    while stack:
        node = stack.pop()
        if node is None:
            out.append("#")
            continue
        out.append(str(node.val))
        stack.append(node.right)
        stack.append(node.left)
    return ",".join(out)


def deserialize(data):
    tokens = iter(data.split(","))
    root_holder = TreeNode(0)
    stack = [(root_holder, "left")]
    for tok in tokens:
        parent, side = stack.pop()
        if tok == "#":
            continue
        node = TreeNode(int(tok))
        setattr(parent, side, node)
        stack.append((node, "right"))
        stack.append((node, "left"))
    return root_holder.left

Follow-ups interviewers ask

Serialise a BST more compactly (no null markers needed).
N-ary tree.

Frequently asked interview questions

Core interview concepts, complexities, and follow-ups scored by hiring teams.

What is the time complexity of Serialize and Deserialize a Binary Tree in Python?

The optimal solution runs in O(n) time and O(n) auxiliary space. Each node is written and read once; the string and the stack are O(n).

What is the brute-force approach, and how do you optimise it?

Pre-order with null markers: O(n) time, O(n) space. Null markers make the structure unambiguous. Level-order (BFS): O(n) time, O(n) space. The LeetCode display format.

What follow-up questions do interviewers ask about Serialize and Deserialize a Binary Tree?

Serialise a BST more compactly (no null markers needed). N-ary tree.