Serialize and Deserialize Binary Tree

The problem

Design two functions for a binary tree.

• serialize(root) turns the tree into a single string.
• deserialize(data) takes that string and rebuilds the exact same tree: the same values in the same places.

You choose the string format. The only rule is that deserialize(serialize(root)) must give back a tree equal to root. The functions must not keep any state between calls.

Trees in the examples are written level by level, from left to right. null marks a missing child.

Example 1

Input: root = [6, 2, 9, null, null, 7]

Output: [6, 2, 9, null, null, 7]

Any format works if it round-trips. The one on this page writes 6,2,#,#,9,7,#,#,#.

one possible string

62##97###

Example 2

Input: root = []

Output: []

The empty tree must survive the round trip too. Our format writes a single #.

Example 3

Input: root = [-5, null, 4]

Output: [-5, null, 4]

Negative values and a missing left child must both come back as they were.

Constraints

• The tree has n nodes, where 0 ≤ n ≤ 10,000.
• -1,000 ≤ Node.val ≤ 1,000

Clarifying questions

Is the string format fixed?

No. Any format is fine as long as deserialize rebuilds the same tree.

Can values be negative or have several digits?

Yes. So values need a separator, such as a comma, or "12" could be read as 1 and 2.

Can the tree be empty?

Yes. The string must still record that, so deserialize can return None.

Can we store data between the two calls?

No. Everything needed to rebuild the tree must be in the string.

Spot the pattern

A list of values alone loses the shape: many trees share the same pre-order values. But if every empty spot is written down too, the shape is fixed. Reading the list back in the same order rebuilds it, one node per value. Both directions are a tree traversal: the same pre-order recursion, once to write and once to read.

Solutions

Pre-order with markersO(n)

Show all

There is only one approach worth showing. Every node must be written and read once, and this does exactly that in each direction. A level-order format works too, at the same cost.

Pre-order with markers O(n)

The idea

Serialize. Walk the tree in pre-order: write the node’s value, then its left subtree, then its right subtree. When a child is missing, write #. Join everything with commas.

Deserialize. Split the string at the commas and read the tokens in the same order. A # means “empty here”, so return None. A number means “a node here”: make it, then read its left subtree, then its right subtree, in the same way.

The reader never has to look ahead or count. The # marks tell it exactly where each subtree ends, because every subtree is written as its root followed by two complete subtrees.

Why it is correct: the reader makes the same calls in the same order as the writer. Each token is read by the call that matches the call that wrote it, so every node ends up in its old place.

Walkthrough

written

1. def serialize(node, parts):
2. if node is None:
3. parts.append("#"); return
4. parts.append(str(node.val))
5. serialize(node.left, parts)
6. serialize(node.right, parts)
7. def deserialize(tokens):
8. token = next(tokens)
9. if token == "#": return None
10. node = TreeNode(int(token))
11. node.left = deserialize(tokens)
12. node.right = deserialize(tokens)
13. return node

Serialize: walk the tree in pre-order (node, left subtree, right subtree) and write each value. Write # for every empty spot, so the shape is kept.

← BackStep →Play1 / 17

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// Pre-order with a marker for every empty spot. The markers fix the
// shape, so one list is enough to rebuild the tree. n steps each way.
class Codec {
    public String serialize(TreeNode root) {
        List<String> parts = new ArrayList<>();
        walk(root, parts);
        return String.join(",", parts);
    }

    private void walk(TreeNode node, List<String> parts) {
        // "#" records an empty spot, so the shape is kept.
        if (node == null) {
            parts.add("#");
            return;
        }
        // Node first, then its subtrees: the reader meets the
        // root of each part before the part itself.
        parts.add(String.valueOf(node.val));
        walk(node.left, parts);
        walk(node.right, parts);
    }

    private String[] tokens;
    private int position;

    public TreeNode deserialize(String data) {
        tokens = data.split(",");
        position = 0;
        return read();
    }

    private TreeNode read() {
        // Read in the same order as the writer wrote.
        String token = tokens[position++];
        if (token.equals("#")) return null;
        TreeNode node = new TreeNode(Integer.parseInt(token));
        // The left subtree was written first, so read it first.
        // Its own "#" marks tell us where it ends.
        node.left = read();
        node.right = read();
        return node;
    }
}

Big O

Time O(n)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   There is no loop. Both functions repeat through recursion, so we count the calls. A serialize call writes one token. A deserialize call reads one token. Each is a fixed job, so each call counts as 1 step. Splitting and joining the string touch each token once more.

   1. def serialize(node, parts):
   2. if node is None:
   3. parts.append("#"); return
   4. parts.append(str(node.val))
   5. serialize(node.left, parts)
   6. serialize(node.right, parts)
   7. def deserialize(tokens):
   8. token = next(tokens)
   9. if token == "#": return None
   10. node = TreeNode(int(token))
   11. node.left = deserialize(tokens)
   12. node.right = deserialize(tokens)
   13. return node

2. 2 Count the runs on Example 1

   Example 1 has 4 nodes and 5 empty spots. Serialize makes one call for each of them and writes 9 tokens. Deserialize reads the same 9 tokens, one call each.

   9 + 9 = 18 calls.

   	nodes	empty spots	calls
   serialize	4	5	9
   deserialize	4	5	9
   total			18

3. 3 Write the count for any n

   A binary tree with n nodes has n + 1 empty spots, so the string has 2n + 1 tokens. Each direction makes one call per token:

   (2n + 1) + (2n + 1) = 4n + 2 calls

   Check it with Example 1: 4 × 4 + 2 = 18. The join and the split add 2n + 1 steps each, which only changes the constant.

4. 4 Keep only the part that grows fastest

   • Drop the + 2. A fixed amount does not change the growth.
   • Drop the 4. When n doubles, 4n doubles too.

   What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The list of tokens has 2n + 1 items, and the string holds them all. Each value has at most 5 characters, so the string grows with n. The call stack is at most h deep, where h is the height, and h is at most n. So the space is O(n).

   parts / tokens (2n + 1 items)call stack (h frames)

Very deep trees

Each recursive call waits until the calls below it finish. If the tree is one long line of 10,000 nodes, that is 10,000 calls waiting at once. The algorithm is still right, but every language limits how many calls can wait, so a very deep tree can crash with a "stack overflow". Here is how to raise the limit:

• Python: stops at 1,000 calls. The code above raises it with sys.setrecursionlimit.
• Java: run with java -Xss64m, or run the work in new Thread(null, task, "main", 64L << 20).
• C#: run the work in new Thread(task, 64 * 1024 * 1024).
• TypeScript (Node): run with node --stack-size=30000.
• Go: nothing to do. Its stack grows by itself.

Recursion is still the answer interviewers expect for trees. Mention the limit out loud: "for a very deep tree, I would raise the stack limit or keep my own stack in a loop."

Common mistake

Writing only the values

Without the # marks, the trees [3, 1] and [3, null, 1] both write 3,1. The reader cannot tell whether 1 is a left or a right child. Every empty spot must be in the string.

Tested at the limits

2,000 random trees of 0 to 12 nodes, in every shape, with values like -1,000, -10, 0 and 42. Pre-order with markers wrote each tree to text, a new Codec read it back, and the tree came back exactly the same every time.

Largest inputs	Result
10,000 nodes (the most allowed), balanced, written and read back. Pre-order with markers.	0.007 s, and about 2 MB of extra memory: the text, its pieces and the new tree, which is the O(n) space.
10,000 nodes in one long line, written and read back. Pre-order with markers.	0.009 s, and about 3 MB of extra memory: the same, plus 10,000 calls that wait at once.