Serialize and Deserialize Binary Tree

Ishaan S Published 24 Oct, 2026

Design a class Codec with two methods:

serialize(root) takes the root of a binary tree and returns a string that encodes it.
deserialize(data) takes a string produced by serialize and rebuilds the tree.

The string format is entirely your choice. The only requirement is that deserialize(serialize(root)) produces a tree with exactly the same shape and the same value at every node. The tree may be empty, and values may repeat.

The judge passes in a tree written as a level-order array with null for missing children, for example [8, 3, 10, null, 6], and checks the tree you rebuild against it. It may use separate Codec instances for the two calls, so keep no state between them.

Example 1

Input: root = [8,3,10,null,6,null,14,4,7] Output: [8,3,10,null,6,null,14,4,7] (decode(encode(x)) gives back the original) Why: Any encoding works, for example "8,3,10,#,6,#,14,4,7,#,..." with # for empty children, as long as decoding it rebuilds this exact tree.

Example 2

Input: root = [] Output: [] (decode(encode(x)) gives back the original) Why: The empty tree must survive the round trip too: decoding its encoding returns null.

Example 3

Input: root = [-7] Output: [-7] (decode(encode(x)) gives back the original) Why: A single node with a negative value. Make sure the minus sign survives your format.

Constraints

The tree has between 0 and 10⁴ nodes.
-1000 <= Node.val <= 1000

Pattern Path · Trees: BFS · problem 97 of 169

A pre-order or level-order list of values alone is ambiguous: several different shapes can produce the same list. What extra information removes the ambiguity?

Record the empty children too, using a marker such as #. With those markers, one traversal fully describes the tree.

If you write the tree level by level with a queue, you can rebuild it the same way: each node you pop from the queue takes the next two tokens as its children.

Target: O(n) time, O(n) extra space.

Start simple

Store both the pre-order and in-order value sequences and rebuild the tree from the pair: O(n) with a hash map, but it only works when all values are distinct, which this problem does not promise.

The key idea

A single traversal order (pre-order, level order, ...) is not enough by itself, because different shapes can give the same value sequence. The fix is to also write down the missing children. With a marker such as # for every empty slot, the sequence pins down the shape exactly.

serialize: walk the tree level by level with a queue. For a real node, output its value and enqueue both children, even empty ones. For an empty slot, output #. Join the tokens with commas.

deserialize: split the string into tokens. The first token is the root, or # for an empty tree. Then repeat the walk: pop a node from the queue, and the next two tokens are its left and right child. Each non-# token becomes a new node that joins the queue. This works because serialize emitted exactly two child tokens for every real node, in the same queue order.

An iterative queue also avoids recursion-depth limits on very deep, skewed trees. A recursive pre-order version with null markers is an equally good answer when recursion depth is not a concern.

Complexity

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

Python

class Codec:
    def serialize(self, root: Optional[TreeNode]) -> str:
        """Level-order walk; '#' marks every missing child."""
        tokens = []
        queue = deque([root])
        while queue:
            node = queue.popleft()
            if node is None:
                tokens.append("#")
            else:
                tokens.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
        return ",".join(tokens)

    def deserialize(self, data: str) -> Optional[TreeNode]:
        tokens = data.split(",")
        if tokens[0] == "#":
            return None
        root = TreeNode(int(tokens[0]))
        queue = deque([root])
        i = 1
        while queue:
            node = queue.popleft()
            # The next two tokens are this node's left and right child.
            if tokens[i] != "#":
                node.left = TreeNode(int(tokens[i]))
                queue.append(node.left)
            if tokens[i + 1] != "#":
                node.right = TreeNode(int(tokens[i + 1]))
                queue.append(node.right)
            i += 2
        return root

JavaScript

class Codec {
  // Level-order walk; '#' marks every missing child.
  serialize(root) {
    const tokens = [];
    const queue = [root];
    for (let head = 0; head < queue.length; head++) {
      const node = queue[head];
      if (node === null) {
        tokens.push("#");
      } else {
        tokens.push(String(node.val));
        queue.push(node.left, node.right);
      }
    }
    return tokens.join(",");
  }

  deserialize(data) {
    const tokens = data.split(",");
    if (tokens[0] === "#") return null;
    const root = new TreeNode(Number(tokens[0]));
    const queue = [root];
    let i = 1;
    for (let head = 0; head < queue.length; head++) {
      const node = queue[head];
      // The next two tokens are this node's left and right child.
      if (tokens[i] !== "#") {
        node.left = new TreeNode(Number(tokens[i]));
        queue.push(node.left);
      }
      if (tokens[i + 1] !== "#") {
        node.right = new TreeNode(Number(tokens[i + 1]));
        queue.push(node.right);
      }
      i += 2;
    }
    return root;
  }
}

What the interviewer is checking

The interviewer wants to see you notice why a plain traversal is ambiguous, pick a format that encodes the shape, and write a decoder that mirrors the encoder exactly, including the empty tree.

Mistakes to avoid

Leaving out null markers, so different tree shapes give the same string.
Parsing values character by character, which breaks on multi-digit and negative numbers; split on a delimiter instead.
Forgetting the empty tree, or crashing when the input string encodes only #.
Recursing on a very deep, skewed tree and hitting the recursion limit.

Follow-ups to expect

How would you make the string as short as possible? (Trim trailing markers, binary encoding.)
What changes for a binary search tree? (Pre-order alone suffices; no markers.)
How would you serialize an N-ary tree? (Store each node's child count.)

In real software

Saving a parsed syntax tree, caching a decision tree model to disk, or sending a DOM-like structure over the network all require turning a pointer-based tree into a flat string and back.

Practice next

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        return "";
    }

// Decodes your encoded string back to a tree.
    public TreeNode deserialize(String data) {
        return null;
    }
}

public class Main {
    // Prints the tree in level order, with null for missing children.
    static String levelOrder(TreeNode root) {
        List<String> out = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode n = q.poll();
            if (n == null) { out.add("null"); continue; }
            out.add(String.valueOf(n.val));
            q.add(n.left);
            q.add(n.right);
        }
        while (!out.isEmpty() && out.get(out.size() - 1).equals("null")) out.remove(out.size() - 1);
        return out.toString();
    }

public static void main(String[] args) {
        // [8, 3, 10, null, 6, null, 14, 4, 7]
        TreeNode root = new TreeNode(8);
        root.left = new TreeNode(3);
        root.right = new TreeNode(10);
        root.left.right = new TreeNode(6);
        root.right.right = new TreeNode(14);
        root.left.right.left = new TreeNode(4);
        root.left.right.right = new TreeNode(7);
        String data = new Codec().serialize(root);
        System.out.println(levelOrder(new Codec().deserialize(data))); // [8, 3, 10, null, 6, null, 14, 4, 7]
    }
}

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        return "";
    }

// Decodes your encoded string back to a tree.
    TreeNode* deserialize(string data) {
        return nullptr;
    }
};

// Prints the tree in level order, with null for missing children.
void printLevelOrder(TreeNode* root) {
    vector<string> out;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* n = q.front(); q.pop();
        if (!n) { out.push_back("null"); continue; }
        out.push_back(to_string(n->val));
        q.push(n->left);
        q.push(n->right);
    }
    while (!out.empty() && out.back() == "null") out.pop_back();
    for (auto& s : out) cout << s << ' ';
    cout << endl;
}

int main() {
    // [8, 3, 10, null, 6, null, 14, 4, 7]
    TreeNode* root = new TreeNode(8);
    root->left = new TreeNode(3);
    root->right = new TreeNode(10);
    root->left->right = new TreeNode(6);
    root->right->right = new TreeNode(14);
    root->left->right->left = new TreeNode(4);
    root->left->right->right = new TreeNode(7);
    string data = Codec().serialize(root);
    printLevelOrder(Codec().deserialize(data));  // 8 3 10 null 6 null 14 4 7
}

class Codec:
    def serialize(self, root: Optional[TreeNode]) -> str:
        """Level-order walk; '#' marks every missing child."""
        tokens = []
        queue = deque([root])
        while queue:
            node = queue.popleft()
            if node is None:
                tokens.append("#")
            else:
                tokens.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
        return ",".join(tokens)

def deserialize(self, data: str) -> Optional[TreeNode]:
        tokens = data.split(",")
        if tokens[0] == "#":
            return None
        root = TreeNode(int(tokens[0]))
        queue = deque([root])
        i = 1
        while queue:
            node = queue.popleft()
            # The next two tokens are this node's left and right child.
            if tokens[i] != "#":
                node.left = TreeNode(int(tokens[i]))
                queue.append(node.left)
            if tokens[i + 1] != "#":
                node.right = TreeNode(int(tokens[i + 1]))
                queue.append(node.right)
            i += 2
        return root

Topics #097 #t-tree-bfs BFS Hard Practice String Tree