Serialize and Deserialize BST — LC 449 Compact Preorder

Problem Statement#

Design an algorithm to serialize and deserialize a binary search tree. The encoded string should be as compact as possible. Encoding/decoding need not follow any particular protocol but it must be your own.

Constraints:

• The number of nodes is in the range [0, 10^4]
• 0 <= Node.val <= 10^4
• Tree is guaranteed to be a BST

Input:  root = [2,1,3]
Encoded: "2 1 3"
Decoded: [2,1,3]

Input:  root = []
Encoded: ""
Decoded: []

Why This Problem Matters#

LeetCode 449 Serialize and Deserialize BST is asked at Amazon, Google, Meta, and Microsoft. Unlike LC 297 (general binary tree), 449 specifically rewards exploiting the BST ordering: a preorder traversal alone suffices to uniquely reconstruct the tree, no null markers needed.

This makes 449 a perfect interview question for testing whether candidates spot domain-specific shortcuts. A candidate who treats it like LC 297 produces a 2x-larger encoding and earns "correct but not optimal." A candidate who recognizes the BST invariant produces compact output and earns full marks.

The pattern matters in production: persisting indexes, snapshotting BSTs across processes, and network-efficient tree replication.

The Core Insight#

A BST is uniquely determined by its preorder traversal because the BST ordering disambiguates left vs right children. Given a preorder sequence and a value range [lo, hi], the first value v in range becomes the root; all subsequent values less than v go to the left subtree (range [lo, v - 1]), and the rest go to the right (range [v + 1, hi]).

Serialization: preorder traversal, append space-separated values.

Deserialization: maintain a pointer/index into the value list. Recursively call with shrinking ranges. When the next value falls out of range, return null without consuming it — the parent will handle it.

Visual Dry Run#

Tree: [5,3,7,2,4,6,8] -> preorder: 5 3 2 4 7 6 8

Deserialize with lo = -inf, hi = inf:

Reconstructed correctly using ranges only.

Solution (Optimal)#

class Codec:
    def serialize(self, root):
        out = []
        def pre(node):
            if not node:
                return
            out.append(str(node.val))
            pre(node.left)
            pre(node.right)
        pre(root)
        return ' '.join(out)
 
    def deserialize(self, data):
        if not data:
            return None
        vals = list(map(int, data.split()))
        self.idx = 0
        def build(lo, hi):
            if self.idx >= len(vals):
                return None
            v = vals[self.idx]
            if v < lo or v > hi:
                return None
            self.idx += 1
            node = TreeNode(v)
            node.left = build(lo, v - 1)
            node.right = build(v + 1, hi)
            return node
        return build(float('-inf'), float('inf'))

var serialize = function(root) {
    const out = [];
    const pre = (node) => {
        if (!node) return;
        out.push(node.val);
        pre(node.left);
        pre(node.right);
    };
    pre(root);
    return out.join(' ');
};
 
var deserialize = function(data) {
    if (!data) return null;
    const vals = data.split(' ').map(Number);
    let idx = 0;
    const build = (lo, hi) => {
        if (idx >= vals.length) return null;
        const v = vals[idx];
        if (v < lo || v > hi) return null;
        idx++;
        const node = new TreeNode(v);
        node.left = build(lo, v - 1);
        node.right = build(v + 1, hi);
        return node;
    };
    return build(-Infinity, Infinity);
};

Time: O(n) for both serialize and deserialize — each node visited once. Space: O(n) for the output string and O(h) for the recursion stack.

Common Mistakes#

• Adding null markers — wastes space; BST does not need them.
• Using a queue without thinking about indexing — works but adds overhead.
• Not converting to integers in deserialize — string compare yields wrong tree.
• Forgetting to idx += 1 only after consuming — duplicates or skips values.
• Treating it like LC 297 (general tree) and missing the BST optimization.

Interview Tips#

• Lead with: "This is a BST, so I can skip null markers — the values' magnitudes encode shape."
• Sketch a small tree, write its preorder, and explain the range-based reconstruction.
• Confirm input edge case: empty tree returns empty string and reconstructs to None.
• Mention space savings vs LC 297: roughly half on a balanced tree, much more on sparse trees.

Follow-up Questions#

• What if duplicates are allowed? Choose <= or >= consistently in range comparisons.
• Postorder instead? Yes, with reversed range logic — last element is root.
• Network format with binary? Pack 4 bytes per int — even more compact.
• Streaming deserialization? Replace index with iterator/generator.
• General binary tree (LC 297)? Add null markers since values do not encode structure.

Key Takeaways#

• LeetCode 449 is a Medium-difficulty FAANG BST serialization question asked at Amazon, Google, and Meta.
• A BST is uniquely determined by its preorder traversal — null markers are unnecessary.
• Reconstruction uses min-max bounds: each value falls into exactly one valid subtree position.
• Time O(n) for both operations; space O(n) for the encoded string.
• Compared to LC 297 (general tree), this approach roughly halves encoded size on balanced trees.
• Always cast tokens to integers during decode — string compare breaks ordering.
• The pattern transfers to BST diffing, replication, and persisted index formats.