Course4all
Join us on telegram
Home/dsa/Trees/Serialize and Deserialize Binary Tree

Serialize and Deserialize Binary Tree

Master this topic with zero to advance depth.

Serialize and Deserialize Binary Tree

Tree to string and back.

Medium
Approach 1

Level I: BFS (Level Order)

Intuition

Standard level-order traversal (BFS) using a queue allows us to convert the tree into a list of strings. Empty children are represented as '#'.

Thought Process

  1. Use a queue to traverse the tree level by level.
  2. For each node, append its value to the result string.
  3. If a child is null, append '#' instead.
  4. When deserializing, split by ',' and use a queue to reconstruct parent-child links.
⏱ O(N)💾 O(N)

Detailed Dry Run

TreeSerialized String
[1, 2, 3]"1,2,3,#,#,#,#"
[1, null, 2]"1,#,2,#,#"
java
public class Codec {
    public String serialize(TreeNode root) {
        if (root == null) return "";
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        StringBuilder res = new StringBuilder();
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node == null) {
                res.append("#, ");
                continue;
            }
            res.append(node.val + ", ");
            q.add(node.left);
            q.add(node.right);
        }
        return res.toString();
    }

    public TreeNode deserialize(String data) {
        if (data == "") return null;
        String[] values = data.split(", ");
        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        for (int i = 1; i < values.length; i++) {
            TreeNode parent = q.poll();
            if (!values[i].equals("#")) {
                parent.left = new TreeNode(Integer.parseInt(values[i]));
                q.add(parent.left);
            }
            if (!values[++i].equals("#")) {
                parent.right = new TreeNode(Integer.parseInt(values[i]));
                q.add(parent.right);
            }
        }
        return root;
    }
}
Approach 2

Level II: Postorder DFS

Intuition

Postorder traversal (Left, Right, Root) is also a valid way to serialize. Deserialization starts from the end of the list and builds the root first, then the right child, then the left child.

Logic

  • Serialize: dfs(left), dfs(right), append(val).
  • Deserialize: Pop from end of list, read val, then root.right = dfs(), root.left = dfs().
⏱ O(N)💾 O(N)

Detailed Dry Run

Serialize [1, 2, 3] -> [#, #, 2, #, #, 3, 1]. Pop 1 (root), then 3 (right), then 2 (left).

java
public class Codec {
    public String serialize(TreeNode root) {
        List<String> list = new ArrayList<>();
        post(root, list);
        return String.join(",", list);
    }
    private void post(TreeNode n, List<String> l) {
        if (n == null) { l.add("#"); return; }
        post(n.left, l); post(n.right, l); l.add(String.valueOf(n.val));
    }
    public TreeNode deserialize(String data) {
        Deque<String> dq = new LinkedList<>(Arrays.asList(data.split(",")));
        return build(dq);
    }
    private TreeNode build(Deque<String> dq) {
        String s = dq.pollLast();
        if (s.equals("#")) return null;
        TreeNode n = new TreeNode(Integer.parseInt(s));
        n.right = build(dq); n.left = build(dq);
        return n;
    }
}
Approach 3

Level III: Optimal (Preorder DFS)

Intuition

Thought Process

Preorder DFS (Root, Left, Right) is more compact and easier to code recursively. We use a List or a String Join for serialization. During deserialization, we convert the string back into a Queue or use an index, then recursively rebuild the structure.

Patterns

DFS Preorder Serialization: Maintain structure by marking leaves explicitly.

Complexity

  • Time: O(N)O(N)
  • Space: O(N)O(N)
⏱ O(N)💾 O(N)

Detailed Dry Run

NodeActionSerialized
1Visit[1]
2Visit[1, 2]
nullVisit[1, 2, #]
nullVisit[1, 2, #, #]
java
public class Codec {
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        encode(root, sb);
        return sb.toString();
    }
    private void encode(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append("#, ");
            return;
        }
        sb.append(node.val + ", ");
        encode(node.left, sb);
        encode(node.right, sb);
    }
    public TreeNode deserialize(String data) {
        Queue<String> q = new LinkedList<>(Arrays.asList(data.split(", ")));
        return decode(q);
    }
    private TreeNode decode(Queue<String> q) {
        String s = q.poll();
        if (s.equals("#")) return null;
        TreeNode node = new TreeNode(Integer.parseInt(s));
        node.left = decode(q);
        node.right = decode(q);
        return node;
    }
}

⚠️ Common Pitfalls & Tips

Be aware of recursion limits for very large trees. Serialization strings can become very large, so StringBuilder (Java) or join (Python) is much faster than string concatenation.

← Previous QuestionPopulating Next Right Pointers in Each Node
Next Question →Binary Tree Maximum Path Sum