Course4all

Serialize and Deserialize Binary Tree

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Trees.

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.

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionPopulating Next Right Pointers in Each Node
Next Question →Binary Tree Maximum Path Sum