Problem 17.13 · Binary TreesHard

Serialize and Deserialize Binary Tree

What it teaches: Turning a tree into text and back: a pre-order walk that writes a marker for every missing child.

Practise it on judges as “Serialize and Deserialize Binary Tree”.

In plain words

Imagine phoning a friend to describe a family tree so they can draw exactly the same picture. You can't send the drawing, only words. If you say every name in a fixed order and also say "nobody here" wherever a child is missing, your friend can rebuild the tree perfectly.

That's the task: write serialize(root) that turns a tree into one string, and deserialize(text) that rebuilds the identical tree from it. The tests call roundTrip(root), which does both, and check that the tree you get back matches the original.

The problem

Design String serialize(TreeNode root) and TreeNode deserialize(String data) so that deserialize(serialize(root)) returns a tree with the same shape and values. Any text format is allowed. roundTrip (already written in the starter) calls both.

Example 1

Input: root = [1, 2, 3, null, null, 4, 5]
Output: [1, 2, 3, null, null, 4, 5]

One possible text: "1,2,#,#,3,4,#,#,5,#,#".

Constraints

0 ≤ nodes ≤ 10⁴
−1000 ≤ value ≤ 1000

Pattern clues in the wording

→ Convert a structure to text and back
→ Shape must be preserved exactly

These clues point to Tree DFS: Recurse into the left and right children and combine what they return (height, sums, paths).

Stuck? Take one hint at a time

Solution · starter

import java.util.*;

class Solution {
    public TreeNode roundTrip(TreeNode root) {
        return deserialize(serialize(root));
    }

    String serialize(TreeNode root) {
        return "";
    }

    TreeNode deserialize(String data) {
        return null;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	root = [1,2,3,null,null,4,5]	[1,2,3,null,null,4,5]
2	root = []	[]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Pre-order with null markers · O(n)2. Level order with null markers · O(n)

Pre-order with null markers

Time O(n) Space O(n)

serialize: pre-order DFS appending each value, or # for null, separated by commas.

deserialize: split into tokens and read them with an index that moves forward: build(node) = token is # ? null : new node, then left = build(), right = build().

▶ Dry run: serialize([1, 2, 3, null, null, 4, 5])root = [1, 2, 3, null, null, 4, 5]

text(list)

Step 1/4Visit the root first: write 1.

Approach 1

import java.util.*;

class Solution {
    public TreeNode roundTrip(TreeNode root) {
        return deserialize(serialize(root));
    }

    String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        write(root, sb);
        return sb.toString();
    }

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

    private int pos;

    TreeNode deserialize(String data) {
        String[] tokens = data.split(",");
        pos = 0;
        return read(tokens);
    }

    private TreeNode read(String[] tokens) {
        String t = tokens[pos++];
        if (t.equals("#")) return null;
        TreeNode n = new TreeNode(Integer.parseInt(t));
        n.left = read(tokens);
        n.right = read(tokens);
        return n;
    }
}

Verdict: Each node and each null is written and read once.

Level order with null markers

Time O(n) Space O(n)

BFS writing children of every real node (including # for missing ones); rebuild by attaching children to nodes in the same queue order. This is the same format the problems on this site use for tree inputs.

Approach 2

import java.util.*;

class Solution {
    public TreeNode roundTrip(TreeNode root) {
        return deserialize(serialize(root));
    }

    String serialize(TreeNode root) {
        if (root == null) return "";
        StringBuilder sb = new StringBuilder();
        Deque<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        sb.append(root.val);
        while (!q.isEmpty()) {
            TreeNode n = q.poll();
            for (TreeNode c : new TreeNode[]{n.left, n.right}) {
                sb.append(',');
                if (c == null) sb.append('#');
                else { sb.append(c.val); q.offer(c); }
            }
        }
        return sb.toString();
    }

    TreeNode deserialize(String data) {
        if (data.isEmpty()) return null;
        String[] t = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(t[0]));
        Deque<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        int i = 1;
        while (!q.isEmpty()) {
            TreeNode n = q.poll();
            if (!t[i].equals("#")) { n.left = new TreeNode(Integer.parseInt(t[i])); q.offer(n.left); }
            i++;
            if (!t[i].equals("#")) { n.right = new TreeNode(Integer.parseInt(t[i])); q.offer(n.right); }
            i++;
        }
        return root;
    }
}

Verdict: Avoids deep recursion on very tall trees.

Before you submit

Edge cases and common mistakes

Test these inputs

Empty tree
Negative values
A tall, one-sided tree (deep recursion)

Mistakes people make

Writing only the values without null markers (the shape is lost).
Using a separator that can appear inside a value.

Interview

Follow-up questions

How would you serialize a BST more compactly?

Command Palette