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, Python, C++ and JavaScript, 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.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 4 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

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.

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 code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Level order with null markersO(n)O(n)
Preorder DFS with null markersO(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.

  1. serialize: BFS; append val or # for each polled node.
  2. deserialize: first value is the root; for each node in a queue, read two tokens for its children.
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.

  1. serialize(n): null → '#,'; else val + ',' + serialize(left) + serialize(right).
  2. deserialize: iterator over tokens; build() recursively.
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.