297. Serialize and Deserialize Binary Tree

NeetCode: Serialize and Deserialize Binary Tree · LeetCode: 297. Serialize and Deserialize Binary Tree · Difficulty: Hard

Design serialize (tree to string) and deserialize (string to the same tree). Any format is fine as long as the round trip restores the tree exactly.

Example

Input:  [1, 2, 3, null, null, 4, 5]
serialize -> "1,2,3,N,N,4,5"   (level order)  or  "1,2,N,N,3,4,N,N,5,N,N"   (preorder)
deserialize(serialize(tree)) == tree

The simplest design is a preorder (DFS) walk with a marker for every missing child. A level-order (BFS) encoding also works, but it needs a queue on both sides and is longer to decode, so this solution uses preorder.

Trees are given in LeetCode's level-order array form: the root first, then each level from left to right, with null marking a missing node, so [1, 2, 3, 4, 5] is the tree above. The tree(Integer... values) helper in each program builds a TreeNode from such an array by filling children from a queue. TreeNode has the fields val, left, and right. A missing child is null: Java object references are nullable and the fields are mutable, so no wrapper type is needed. LeetCode names the class Codec, with serialize(TreeNode root) and deserialize(String data).

Optimal: preorder (DFS) with N markers

Write the root, then the left subtree, then the right subtree, using N for every missing child. That listing is unambiguous, so decoding reads tokens in the same order: read one token; if it is N return null, otherwise make a node and let the next recursive calls build its left and right subtrees from the following tokens. No queue is needed. The tokens are held in an Iterator<String>, an object that returns the next element on each next() call, so every recursive call continues where the previous one stopped.

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Iterator;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

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

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

    public TreeNode deserialize(String data) {
        return build(Arrays.asList(data.split(",")).iterator());
    }

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

public class Main {
    /** Builds a tree from LeetCode's level-order array, where null marks a missing node. */
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) return null;
        TreeNode root = new TreeNode(values[0]);
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.poll();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        Codec codec = new Codec();
        TreeNode original = tree(1, 2, 3, null, null, 4, 5);
        String text = codec.serialize(original);
        System.out.println(text);
        TreeNode restored = codec.deserialize(text);
        System.out.println(codec.serialize(restored).equals(text));
        System.out.println(codec.serialize(codec.deserialize("N")));
        System.out.println(codec.serialize(codec.deserialize(codec.serialize(tree(-5, Integer.MIN_VALUE, 0)))));
    }
}

1,2,N,N,3,4,N,N,5,N,N
true
N
-5,-2147483648,N,N,0,N,N

The last line serializes, decodes, and serializes again a tree holding -5, Integer.MIN_VALUE, and 0. Negative values and Integer.MIN_VALUE round-trip because Integer.parseInt reads the leading -, and the marker N cannot be mistaken for a number. Time: O(n). Space: O(n) for the string and O(h) for the recursion.

Level order (BFS) is the other standard format: serialize with a queue that also holds missing children, and decode by attaching two tokens per queued node. It has the same complexity.

How to explain it in an interview

• Say first: any unambiguous encoding works, for example a preorder listing with N for every empty child.
• Key insight: recording the empty children makes preorder unambiguous, so the decoder can rebuild by consuming tokens in the same order: one token, then the whole left subtree, then the whole right subtree.
• Code it in steps: (1) serialize recursively with a StringBuilder: N for null, else val then left then right; (2) deserialize splits on commas into an iterator; (3) build takes the next token, returns null for N, otherwise parses the value and builds left then right from the same iterator.
• Complexity to state: time O(n), space O(n) for the string plus O(h) recursion.
• Likely follow-ups / pitfalls: "why not inorder?" (an inorder listing does not say which value is the root, so it cannot be decoded alone); the BFS format is the alternative; deep skewed trees can overflow the recursion stack, which an explicit stack avoids; building the string with + in a loop would be O(n²).