☕ DSA Java Articles

Topics › Binary Trees › Hard Problems

Serialize and De-serialize BT

Hard TUF ID 112 A2ZSDEBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Design two functions. serialize(root) turns a binary tree into a string. deserialize(data) takes such a string and rebuilds a tree that is identical to the original: same shape, same values in the same places. You choose the string format; the only requirement is that the two functions agree.

Constraints (LeetCode version): up to 10^4 nodes, values in [-1000, 1000]. Values may repeat, and the tree can have any shape. The Java file also tests the extreme int values.

Example 1

        1
       / \
      2   3
         / \
        4   5

level-order format:  "1,2,3,#,#,4,5,#,#,#,#,"
preorder format:     "1,2,#,#,3,4,#,#,5,#,#"
deserialize(serialize(root)) gives back this exact tree

Example 2

root = []           // empty tree
level-order format: ""      preorder format: "#"

Why missing children must be written down

A plain traversal such as preorder [1, 2, 3] does not identify a tree: many shapes produce it. Even two traversals only work when one is inorder and all values are distinct, and here values can repeat. The fix is simple: also record where the tree stops. Write a marker (# here) for every missing child. With the markers, the extent of every subtree is visible in the string, so one traversal is enough and duplicates no longer matter, because the decoder never has to search for a value.

A separator (,) is also needed, since values can have several digits and a minus sign.

Approach 1: Level order (BFS)

Intuition. Walk the tree with a queue, level by level. For every real node, write its value and enqueue both children, even the null ones; every null taken from the queue is written as #. The decoder replays the same queue discipline: the nodes it dequeues are exactly the parents, in the same order, and each one owns the next two tokens of the string as its left and right child.

Algorithm.

Serialize.

  1. If the root is null, return "".
  2. Queue the root. Repeatedly dequeue a node: if it is null, append #,; otherwise append value, and enqueue its left and right children (possibly null).

Deserialize.

  1. If the string is empty, return null.
  2. Split on ,. The first token is the root; queue it.
  3. Repeatedly dequeue a parent and read two tokens: each one that is not # becomes a new child, which is enqueued.
static String serializeLevelOrder(TreeNode root) {
    if (root == null) return "";
    StringBuilder sb = new StringBuilder();
    Queue<TreeNode> queue = new LinkedList<>();             // LinkedList accepts null entries, ArrayDeque does not
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode cur = queue.poll();
        if (cur == null) {
            sb.append("#,");
            continue;
        }
        sb.append(cur.val).append(',');
        queue.add(cur.left);
        queue.add(cur.right);
    }
    return sb.toString();
}

static TreeNode deserializeLevelOrder(String data) {
    if (data.isEmpty()) return null;
    String[] parts = data.split(",");
    TreeNode root = new TreeNode(Integer.parseInt(parts[0]));
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    int i = 1;
    while (!queue.isEmpty()) {
        TreeNode cur = queue.poll();                         // the next two tokens are its children
        if (!parts[i].equals("#")) {
            cur.left = new TreeNode(Integer.parseInt(parts[i]));
            queue.add(cur.left);
        }
        i++;
        if (!parts[i].equals("#")) {
            cur.right = new TreeNode(Integer.parseInt(parts[i]));
            queue.add(cur.right);
        }
        i++;
    }
    return root;
}

Dry run of deserializing "1,2,3,#,#,4,5,#,#,#,#," (tokens after the root: 2 3 # # 4 5 # # # #):

dequeued parent left token right token queue afterwards
1 2 3 [2, 3]
2 # # [3]
3 4 5 [4, 5]
4 # # [5]
5 # # []

Every token is consumed exactly once and the queue empties exactly when the tokens run out.

Why the indices never run past the end. A tree with n nodes has n + 1 missing child slots, so the string holds n values and n + 1 markers, 2n + 1 tokens. The decoder reads the root and then two tokens for each of the n real nodes: 1 + 2n, a perfect match.

Two Java details: String.split drops trailing empty strings, so the final comma is harmless; and the serializer uses LinkedList as its queue because ArrayDeque rejects null elements.

Complexity. Time O(n) for each direction: every node and every marker is handled once. Space O(n) for the string and the queue (a level can hold about n / 2 nodes).

Approach 2: Preorder DFS

Intuition. Write the tree in preorder (node, left subtree, right subtree), again with # for every missing child. Decoding uses the same recursion: read one token; if it is #, the subtree is empty; otherwise create the node, then read its left subtree, then its right subtree, from the same stream of tokens.

Why does this work without any lengths or indices? Because the encoding of every subtree is self-delimiting: by induction, readPreorder consumes exactly the tokens that writePreorder produced for one subtree and stops right after them. An empty subtree is one token (#); a node is its value followed by two complete subtrees. So when the left call returns, the stream is positioned exactly at the start of the right subtree.

Algorithm.

  1. Serialize: in preorder, append # for null and the value otherwise, separating tokens with commas.
  2. Deserialize: split into tokens and walk them with an iterator; read a token, return null for #, else build the node and recursively read its left and right children.
static String serializePreorder(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    writePreorder(root, sb);
    return sb.toString();
}

static void writePreorder(TreeNode node, StringBuilder sb) {
    if (sb.length() > 0) sb.append(',');
    if (node == null) {
        sb.append('#');
        return;
    }
    sb.append(node.val);
    writePreorder(node.left, sb);
    writePreorder(node.right, sb);
}

static TreeNode deserializePreorder(String data) {
    Iterator<String> tokens = Arrays.asList(data.split(",")).iterator();
    return readPreorder(tokens);
}

static TreeNode readPreorder(Iterator<String> tokens) {
    String token = tokens.next();
    if (token.equals("#")) return null;
    TreeNode node = new TreeNode(Integer.parseInt(token));
    node.left = readPreorder(tokens);                        // consumes exactly the left subtree's tokens
    node.right = readPreorder(tokens);
    return node;
}

For Example 1 the preorder string is 1,2,#,#,3,4,#,#,5,#,#: the root 1, then the subtree 2,#,#, then the subtree 3,4,#,#,5,#,#.

Complexity. Time O(n) in each direction. Space O(n) for the string and tokens, plus O(h) recursion depth, which is O(n) for a chain.

Which one to choose

Both strings contain the same 2n + 1 tokens, so neither is more compact. The preorder version is shorter to write and easy to reason about. The level-order version is iterative, so it cannot overflow the call stack on a very deep, skewed tree; with 10^4 nodes in a single chain, a recursive solution is close to Java’s default stack limits on some judges. Interviewers accept either; mention the trade-off.

Edge cases and pitfalls

The tests check the exact strings for the example, round-trip both formats on an empty tree, a single node, negative values, Integer.MIN_VALUE and Integer.MAX_VALUE, duplicates, both kinds of chain and a 5000-node balanced tree, and also confirm that re-serializing the rebuilt tree reproduces the same string.