Serialize and Deserialize Binary Tree

Hard Problem 79 of 151 Java and Python

Problem

Design an algorithm to serialize a binary tree into a string and deserialize that string back into the original tree structure.

Implement a Codec class with serialize(root) and deserialize(data). Any format is allowed, as long as deserialize(serialize(root)) gives back the same tree.

Example 1

Input: root = [1, 2, 3, null, null, 4, 5]
Output: [1, 2, 3, null, null, 4, 5]
Why: The tree survives a round trip.

Example 2

Input: root = []
Output: []

Constraints

0 ≤ number of nodes ≤ 10⁴
-1000 ≤ Node.val ≤ 1000

Explanation

A traversal alone loses the shape, but a traversal that also writes null markers for missing children does not: there is only one tree that produces that exact sequence.

Preorder with markers is the simplest to rebuild: read a value, make a node, rebuild its left subtree from the following tokens, then its right subtree.

Approach 1 · Better

Level order (BFS) with markers

Time O(n)
Space O(n)

Write the tree breadth first, the way LeetCode prints trees, and rebuild it with a queue.

Serialize: BFS; write each node's value, or "#" for null, and enqueue children of real nodes.
Deserialize: create the root from the first token; for each node taken from a queue, the next two tokens are its left and right children.

Java

import java.util.*;

class Codec {
    public String serialize(TreeNode root) {
        StringBuilder out = new StringBuilder();
        Deque<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                out.append("#,");
                continue;
            }
            out.append(node.val).append(',');
            queue.add(node.left);
            queue.add(node.right);
        }
        return out.toString();
    }

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

Python

from collections import deque

class Codec:
    def serialize(self, root):
        out, queue = [], deque([root])
        while queue:
            node = queue.popleft()
            if not node:
                out.append("#")
                continue
            out.append(str(node.val))
            queue.append(node.left)
            queue.append(node.right)
        return ",".join(out)

    def deserialize(self, data):
        tokens = data.split(",")
        if tokens[0] == "#":
            return None
        root = TreeNode(int(tokens[0]))
        queue, i = deque([root]), 1
        while queue:
            node = queue.popleft()
            if tokens[i] != "#":
                node.left = TreeNode(int(tokens[i]))
                queue.append(node.left)
            i += 1
            if tokens[i] != "#":
                node.right = TreeNode(int(tokens[i]))
                queue.append(node.right)
            i += 1
        return root

Approach 2 · Optimal

Preorder DFS with markers

Time O(n)
Space O(n)

Serialize recursively in preorder; deserialize by reading tokens in the same order, recursing for the left and right child.

Serialize: null → "#"; otherwise write the value, then serialize left, then right.
Deserialize: read the next token; "#" means null; otherwise make a node and build its left, then right, from the following tokens.

Java

import java.util.*;

class Codec {
    public String serialize(TreeNode root) {
        StringBuilder out = new StringBuilder();
        write(root, out);
        return out.toString();
    }

    private void write(TreeNode node, StringBuilder out) {
        if (node == null) {
            out.append("#,");
            return;
        }
        out.append(node.val).append(',');
        write(node.left, out);
        write(node.right, out);
    }

    public TreeNode deserialize(String data) {
        Iterator<String> tokens = Arrays.asList(data.split(",")).iterator();
        return read(tokens);
    }

    private TreeNode read(Iterator<String> tokens) {
        String token = tokens.next();
        if (token.equals("#")) {
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(token));
        node.left = read(tokens);
        node.right = read(tokens);
        return node;
    }
}

Python

class Codec:
    def serialize(self, root):
        out = []

        def write(node):
            if not node:
                out.append("#")
                return
            out.append(str(node.val))
            write(node.left)
            write(node.right)

        write(root)
        return ",".join(out)

    def deserialize(self, data):
        tokens = iter(data.split(","))

        def read():
            token = next(tokens)
            if token == "#":
                return None
            node = TreeNode(int(token))
            node.left = read()
            node.right = read()
            return node

        return read()

Complexity compared

Approach	Time	Space
Better Level order (BFS) with markers	O(n)	O(n)
Optimal Preorder DFS with markers	O(n)	O(n)

Key takeaways

Null markers are what make a single traversal enough to rebuild the tree.
Very deep trees can overflow the recursion stack; the BFS version avoids that.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem