Serialize and Deserialize BST

medium tree bst dfs design

Problem

Design serialize/deserialize for a BST so that the encoding is compact (no nulls) and deserialize(serialize(root)) yields an equivalent BST.

Inputtree preorder = [8, 5, 1, 7, 10, 12]

Output"8,5,1,7,10,12" → rebuild same BST

Preorder + BST ordering uniquely determines the tree.

preorder (comma-separated)

class Codec:
    def serialize(self, root):
        out = []
        def dfs(n):
            if not n: return
            out.append(str(n.val))
            dfs(n.left); dfs(n.right)
        dfs(root)
        return ",".join(out)

    def deserialize(self, data):
        if not data: return None
        vals = list(map(int, data.split(",")))
        from itertools import count
        it = iter(vals)
        def build(lo, hi, peek=[None]):
            if peek[0] is None:
                try: peek[0] = next(it)
                except StopIteration: return None
            v = peek[0]
            if v < lo or v > hi: return None
            peek[0] = None
            node = TreeNode(v)
            node.left = build(lo, v - 1, peek)
            node.right = build(v + 1, hi, peek)
            return node
        return build(float('-inf'), float('inf'))

class Codec {
  serialize(root) {
    const out = [];
    const dfs = n => { if (!n) return; out.push(n.val); dfs(n.left); dfs(n.right); };
    dfs(root);
    return out.join(",");
  }
  deserialize(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 = { val: v, left: null, right: null };
      node.left = build(lo, v - 1);
      node.right = build(v + 1, hi);
      return node;
    };
    return build(-Infinity, Infinity);
  }
}

public class Codec {
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        dfs(root, sb);
        return sb.toString();
    }
    private void dfs(TreeNode n, StringBuilder sb) {
        if (n == null) return;
        if (sb.length() > 0) sb.append(',');
        sb.append(n.val);
        dfs(n.left, sb); dfs(n.right, sb);
    }
    int idx = 0; int[] vals;
    public TreeNode deserialize(String data) {
        if (data.isEmpty()) return null;
        String[] p = data.split(",");
        vals = new int[p.length];
        for (int i = 0; i < p.length; i++) vals[i] = Integer.parseInt(p[i]);
        idx = 0;
        return build(Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    private TreeNode build(int lo, int hi) {
        if (idx == vals.length) return null;
        int v = vals[idx];
        if (v < lo || v > hi) return null;
        idx++;
        TreeNode n = new TreeNode(v);
        n.left = build(lo, v - 1);
        n.right = build(v + 1, hi);
        return n;
    }
}

class Codec {
public:
    string serialize(TreeNode* root) {
        string s;
        function<void(TreeNode*)> dfs = [&](TreeNode* n) {
            if (!n) return;
            if (!s.empty()) s += ',';
            s += to_string(n->val);
            dfs(n->left); dfs(n->right);
        };
        dfs(root);
        return s;
    }
    int idx = 0; vector<int> vals;
    TreeNode* build(long lo, long hi) {
        if (idx == (int)vals.size()) return nullptr;
        int v = vals[idx];
        if (v < lo || v > hi) return nullptr;
        idx++;
        auto n = new TreeNode(v);
        n->left = build(lo, v - 1);
        n->right = build(v + 1, hi);
        return n;
    }
    TreeNode* deserialize(string data) {
        if (data.empty()) return nullptr;
        idx = 0; vals.clear();
        stringstream ss(data); string tok;
        while (getline(ss, tok, ',')) vals.push_back(stoi(tok));
        return build(LONG_MIN, LONG_MAX);
    }
};

Explanation

For a plain binary tree you'd need to store nulls, but a BST lets us be compact: we save just the preorder sequence of values and no markers at all. The ordering rule does the rest.

Serialize is a straight preorder DFS that appends each value — for our example that's 8, 5, 1, 7, 10, 12.

Deserialize rebuilds using value bounds. build(lo, hi) looks at the next value: if it falls outside (lo, hi) it doesn't belong here, so we return null without consuming it. Otherwise we take it as the current node, then build its left child with the tightened range (lo, v-1) and its right child with (v+1, hi).

Example: starting bounds (-∞, +∞), take 8 as root. Left build with (-∞, 7) takes 5, then under it 1 and 7 fit. Back at the root, the right build with (9, +∞) takes 10 then 12 — exactly the original BST.

The bounds tell each value precisely where it belongs in the tree, so the preorder list alone is enough to rebuild it in linear time without any null placeholders.

Time: O(n) Space: O(n)