Serialize and Deserialize Binary Tree

Hard Trees & BST Tree Serialization / Deserialization Original on LeetCode

Serialize and Deserialize Binary Tree is a hard trees & bst problem solved with the tree serialization / deserialization pattern. The best approach, preorder dfs with null markers, runs in O(n) time and O(n) space. Below are 2 approaches in Java, from level order with null markers up.

Problem

Design a Codec that turns a binary tree into a string (serialize) and turns that string back into an identical tree (deserialize).

Examples

Example 1

Input: root = [1, 2, 3, null, null, 4, 5]
Output: deserialize(serialize(root)) gives the same tree
Why: One possible string: 1,2,#,#,3,4,#,#,5,#,#

Example 2

Input: root = []
Output: []

Constraints

The tree has 0 to 10^4 nodes; values from -1000 to 1000.
Any format works as long as the round trip is exact.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Level order with null markers	`O(n)`	`O(n)`
Preorder DFS with null markers	`O(n)`	`O(n)`

1Level order with null markers

TimeO(n)

SpaceO(n)

Write the tree in BFS order, using # for missing children. To rebuild, read values in the same order and attach them as left and right children of the nodes in a queue.

serialize: BFS; append val or # for each polled node.
deserialize: first value is the root; for each node in a queue, read two tokens for its children.

Java

class Codec {
    public String serialize(TreeNode root) {
        if (root == null) return "";
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode n = q.poll();
            if (n == null) { sb.append("#,"); continue; }
            sb.append(n.val).append(',');
            q.add(n.left);
            q.add(n.right);
        }
        return sb.toString();
    }

    public TreeNode deserialize(String data) {
        if (data.isEmpty()) return null;
        String[] t = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(t[0]));
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        int i = 1;
        while (!q.isEmpty()) {
            TreeNode n = q.poll();
            if (!t[i].equals("#")) { n.left = new TreeNode(Integer.parseInt(t[i])); q.add(n.left); }
            i++;
            if (!t[i].equals("#")) { n.right = new TreeNode(Integer.parseInt(t[i])); q.add(n.right); }
            i++;
        }
        return root;
    }
}

2Preorder DFS with null markers

TimeO(n)

SpaceO(n)

Write node, left subtree, right subtree, with # for null. Reading back uses the same recursion: take a token, # means null, otherwise make a node and read its left then right subtree.

serialize(n): null → '#,'; else val + ',' + serialize(left) + serialize(right).
deserialize: iterator over tokens; build() recursively.

Java

class Codec {
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        write(root, sb);
        return sb.toString();
    }

    private void write(TreeNode n, StringBuilder sb) {
        if (n == null) { sb.append("#,"); return; }
        sb.append(n.val).append(',');
        write(n.left, sb);
        write(n.right, sb);
    }

    public TreeNode deserialize(String data) {
        return read(new ArrayDeque<>(Arrays.asList(data.split(","))));
    }

    private TreeNode read(Deque<String> tokens) {
        String t = tokens.poll();
        if (t.equals("#")) return null;
        TreeNode n = new TreeNode(Integer.parseInt(t));
        n.left = read(tokens);
        n.right = read(tokens);
        return n;
    }
}

Edge cases to test

Empty tree
Negative values
Skewed trees

Hints

Hint 1

Preorder alone is ambiguous, but preorder with a marker for every null child is not.

FAQ

What is the best time complexity for Serialize and Deserialize Binary Tree?

Preorder DFS with null markers runs in O(n) time and O(n) extra space.

Which pattern does Serialize and Deserialize Binary Tree use?

It is a trees & bst problem that uses the tree serialization / deserialization pattern. Other problems with the same pattern: Construct Binary Tree from Preorder and Inorder Traversal, Construct Binary Tree from Inorder and Postorder Traversal, Construct Binary Search Tree from Preorder Traversal.

Is there a brute force solution for Serialize and Deserialize Binary Tree?

Yes. Level order with null markers takes O(n) time and O(n) space. Write the tree in BFS order, using for missing children.

Which edge cases should I test for Serialize and Deserialize Binary Tree?

Empty tree; Negative values; Skewed trees.