Serialize and Deserialize a Binary Tree

Write code to serialize and deserialize a given binary tree.

💡Strategies for Solving This Problem

The Encoding Challenge

This showed up at Amazon in 2024. It's about choosing the right serialization format and handling null nodes correctly.

The Problem

Convert a binary tree to a string, then reconstruct the exact tree from that string. The tree structure must be preserved perfectly, including null nodes.

Approach 1: Level Order (BFS)

Serialize level by level, using a special marker (like "null") for empty nodes.

Example tree:

Serialized: "1,2,3,null,null,4,5"

This is intuitive and produces compact output. Most common approach.

Approach 2: Pre-order (DFS)

Serialize using pre-order traversal (root, left, right), marking nulls.

Same tree: "1,2,null,null,3,4,null,null,5,null,null"

Longer output but easier to deserialize recursively. The null markers tell you when subtrees end.

Which to Use?

Level-order is more common and produces shorter strings. Pre-order is easier to code the deserialization recursively.

I used level-order at Amazon because it's what most people expect and it's more space-efficient.

Key Insight

You MUST encode null nodes. Without them, you can't distinguish between different tree structures that have the same values.

Example: [1,2] could be:

  1          1
 /            
2              2

With nulls: "1,2,null" vs "1,null,2"

At Amazon

Interviewer asked "Why do we need to serialize nulls?" I explained the ambiguity above. Then asked about edge cases: empty tree, single node, long chains.

Also discussed format choices - could use JSON, but string is simpler and faster.

✅Solution

Solution: Level-Order Serialization

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

function serialize(root) {
    if (root === null) return "";

    const result = [];
    const queue = [root];

    while (queue.length > 0) {
        const node = queue.shift();

        if (node === null) {
            result.push("null");
        } else {
            result.push(node.val.toString());
            queue.push(node.left);
            queue.push(node.right);
        }
    }

    return result.join(",");
}

function deserialize(data) {
    if (data === "") return null;

    const values = data.split(",");
    const root = new TreeNode(parseInt(values[0]));
    const queue = [root];
    let i = 1;

    while (queue.length > 0 && i < values.length) {
        const node = queue.shift();

        // Process left child
        if (values[i] !== "null") {
            node.left = new TreeNode(parseInt(values[i]));
            queue.push(node.left);
        }
        i++;

        // Process right child
        if (i < values.length && values[i] !== "null") {
            node.right = new TreeNode(parseInt(values[i]));
            queue.push(node.right);
        }
        i++;
    }

    return root;
}

// Helper to print tree (level order)
function printTree(root) {
    if (root === null) {
        console.log("empty tree");
        return;
    }

    const queue = [root];
    const result = [];

    while (queue.length > 0) {
        const node = queue.shift();
        if (node === null) {
            result.push("null");
        } else {
            result.push(node.val);
            queue.push(node.left);
            queue.push(node.right);
        }
    }

    console.log(result.join(","));
}

// Test
const tree = new TreeNode(1);
tree.left = new TreeNode(2);
tree.right = new TreeNode(3);
tree.right.left = new TreeNode(4);
tree.right.right = new TreeNode(5);

console.log("Original:");
printTree(tree);  // 1,2,3,null,null,4,5,null,null,null,null

const serialized = serialize(tree);
console.log("Serialized:", serialized);

const deserialized = deserialize(serialized);
console.log("Deserialized:");
printTree(deserialized);  // Should match original

Alternative: Pre-order Serialization

function serializePreOrder(root) {
    if (root === null) return "null";

    const left = serializePreOrder(root.left);
    const right = serializePreOrder(root.right);

    return root.val + "," + left + "," + right;
}

function deserializePreOrder(data) {
    const values = data.split(",");
    let index = 0;

    function buildTree() {
        if (values[index] === "null") {
            index++;
            return null;
        }

        const node = new TreeNode(parseInt(values[index]));
        index++;
        node.left = buildTree();
        node.right = buildTree();
        return node;
    }

    return buildTree();
}

// Test
const tree2 = new TreeNode(1);
tree2.left = new TreeNode(2);
tree2.right = new TreeNode(3);
tree2.right.left = new TreeNode(4);
tree2.right.right = new TreeNode(5);

const ser2 = serializePreOrder(tree2);
console.log("Pre-order:", ser2);  // 1,2,null,null,3,4,null,null,5,null,null

const deser2 = deserializePreOrder(ser2);
printTree(deser2);

Step-by-Step: Level-Order Deserialization

String: "1,2,3,null,null,4,5"

i=0: Create root = 1, queue = [1]
i=1: Process node 1
  - Left child: 2 (not null), create it, queue = [2]
i=2: - Right child: 3 (not null), create it, queue = [2,3]
i=3: Process node 2
  - Left child: null, skip
i=4: - Right child: null, skip
i=5: Process node 3
  - Left child: 4 (not null), create it, queue = [4]
i=6: - Right child: 5 (not null), create it, queue = [4,5]
Queue empty, done

Result:
    1
   / 
  2   3
     / 
    4   5

Complexity

Level-Order:

Serialize: O(n) time, O(n) space for queue
Deserialize: O(n) time, O(n) space for queue

Pre-Order:

Serialize: O(n) time, O(h) space for recursion
Deserialize: O(n) time, O(h) space for recursion

Both are O(n) but pre-order has better space for balanced trees (O(log n) vs O(n)).

Common Mistakes

Not encoding nulls: Causes ambiguity in reconstruction
Wrong index tracking: In deserialize, easy to get indices wrong
Not handling empty tree: Return empty string or "null"
Queue management: Must add both children even if null (for level-order)

Follow-Up: Why Not JSON?

Could use JSON.stringify(), but:

Produces longer strings (with quotes, braces)
Less efficient to parse
Custom format is faster and cleaner
Shows you understand serialization fundamentals