60.Serialize and Deserialize Binary Tree

HardBlind 75Trees · 15/15

Problem

Design an algorithm to serialize a binary tree into a string and deserialize that string back into the original tree structure. Implement a class Codec with:

String serialize(TreeNode root) — encodes a tree to a single string.
TreeNode deserialize(String data) — decodes the string back to a tree.

There is no required format; the only requirement is that deserialize(serialize(root)) reproduces the same tree (same shape and values).

Examples

Input:  root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]
Explanation: One possible encoding is "1,2,#,#,3,4,#,#,5,#,#".

Input:  root = []
Output: []

Constraints

The number of nodes in the tree is in the range [0, 10^4].
-1000 <= Node.val <= 1000

💡 Key Insight

A single traversal order of values is ambiguous, but a traversal that also records every null child is not: the null markers tell the decoder exactly where each subtree ends. Both a level-order (BFS) encoding and a pre-order (DFS) encoding with null markers work in O(n); the pre-order version decodes with a natural recursion that mirrors the encoder exactly.

BFS Level Order with Null Markers

TimeO(n)SpaceO(n)

Intuition

This is the format LeetCode itself uses. Encode the tree level by level, writing # for missing children. To decode, read the first token as the root and put it in a queue; then, for each node polled, the next two tokens are its left and right children. Non-null children go into the queue so their own children are read later.

Algorithm

Serialize

If root is null, return "".
BFS from root. For each polled node, append its value or # if it is null; for non-null nodes enqueue both children (even if null).

Deserialize

If data is empty, return null.
Split on ,. Create the root from token 0; enqueue it; i = 1.
While the queue is not empty: poll parent; token i is its left child, token i + 1 its right child (# means null); enqueue non-null children; advance i by 2.

Visualization

Tree:     1
         / \
        2   3
           / \
          4   5

serialize (BFS): "1,2,3,#,#,4,5,#,#,#,#"

deserialize:
  root 1          queue [1]
  poll 1 -> left 2, right 3       queue [2, 3]
  poll 2 -> left #, right #       queue [3]
  poll 3 -> left 4, right 5       queue [4, 5]
  poll 4 -> #, #   poll 5 -> #, #

Code

java

import java.util.LinkedList;
import java.util.Queue;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>(); // LinkedList allows null
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                sb.append("#,");
                continue;
            }
            sb.append(node.val).append(',');
            queue.offer(node.left);
            queue.offer(node.right);
        }
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.isEmpty()) {
            return null;
        }
        String[] tokens = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int i = 1;
        while (!queue.isEmpty()) {
            TreeNode parent = queue.poll();
            // next two tokens are this parent's children
            if (!tokens[i].equals("#")) {
                parent.left = new TreeNode(Integer.parseInt(tokens[i]));
                queue.offer(parent.left);
            }
            i++;
            if (!tokens[i].equals("#")) {
                parent.right = new TreeNode(Integer.parseInt(tokens[i]));
                queue.offer(parent.right);
            }
            i++;
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

Complexity

Time: O(n) — each node and each null child is written once and read once.
Space: O(n) — the string (n values plus n + 1 null markers) and the queue.

Pre-Order DFS with Null MarkersOptimal

TimeO(n)SpaceO(n)

Intuition

Write the tree in pre-order: node value, then the whole left subtree, then the whole right subtree, with # for every null. Decoding is the same recursion run in reverse: read a token — if it is #, this subtree is empty; otherwise create the node, then recursively decode its left subtree, then its right subtree, consuming tokens from a shared cursor. Because the encoder and decoder recurse in the same order, each token is consumed exactly where it was produced. No queue is needed and the logic stays symmetric.

Algorithm

Serialize

dfs(node): if null, append #,; else append val,, then dfs(left), dfs(right).

Deserialize

Split into tokens; set cursor pos = 0.
build(): read tokens[pos++]; if #, return null; else create the node, set node.left = build(), node.right = build(), return it.

Dry Run

flowchart TD
    T["tokens: 1 2 # # 3 4 # # 5 # #"] --> A["read 1 -> node 1"]
    A -->|"left"| B["read 2 -> node 2"]
    B -->|"left / right"| B1["read # #  -> both null"]
    A -->|"right"| C["read 3 -> node 3"]
    C -->|"left"| D["read 4 -> node 4<br/>then # # -> leaf"]
    C -->|"right"| E["read 5 -> node 5<br/>then # # -> leaf"]

Code

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Codec {
    private static final String NULL = "#";
    private static final String SEP = ",";

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        write(root, sb);
        return sb.toString();
    }

    private void write(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append(NULL).append(SEP);
            return;
        }
        sb.append(node.val).append(SEP); // root, then left, then right
        write(node.left, sb);
        write(node.right, sb);
    }

    private String[] tokens;
    private int pos;

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        tokens = data.split(SEP);
        pos = 0;
        return read();
    }

    private TreeNode read() {
        String token = tokens[pos++];
        if (token.equals(NULL)) {
            return null; // empty subtree ends here
        }
        TreeNode node = new TreeNode(Integer.parseInt(token));
        node.left = read();  // decode in the same order we encoded
        node.right = read();
        return node;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

Complexity

Time: O(n) — every node and null marker is written and parsed once.
Space: O(n) — the string and token array, plus O(h) recursion.

Complexity Comparison

Approach	Time	Space
BFS Level Order with Null Markers	O(n)	O(n)
Pre-Order DFS with Null Markers	O(n)	O(n)

Common Pitfalls

Serializing only values (e.g. pre-order without null markers) — [1,2] and [1,null,2] would encode identically and cannot be told apart.
Values can be negative and multi-digit (-1000), so you need a separator; reading one character per node breaks.
Empty tree: in the BFS version "".split(",") returns [""], so guard the empty string before parsing; the DFS version encodes it as "#,", which decodes to null naturally.
Using ArrayDeque to hold null children in the BFS serializer — it throws NullPointerException; use LinkedList.
Keeping state in static fields — ser and deser may be different Codec instances, and LeetCode reuses classes across tests.