Serialize and Deserialize Binary Tree

hardTrees: BST & Advanced136 stepsJava · Python · C++

Turn a tree into a string and back. Write a preorder traversal with # for null children; the markers make the shape unambiguous. To rebuild, read tokens in the same preorder: a number creates a node and recursively builds its left and right subtrees, # returns null.

▶ Watch the animated trace

Traced input: root = [1, 2, 3, null, null, 4, 5] → [1,2,3,null,null,4,5]. Original problem: neetcode.io/problems/serialize-and-deserialize-binary-tree

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(n)

Every node and null child is written and read once.

Key idea

Preorder plus explicit nulls encodes the exact shape.
Deserialization mirrors serialization exactly: same order, same recursion.
A queue of tokens tracks the read position.

Common mistakes

Leaving out null markers: [1, 2] and [1, null, 2] would serialize the same.
String concatenation in a loop is O(n²); use a StringBuilder.
Splitting on "," and forgetting negative numbers have a '-' sign (parseInt handles it).

Solution

Java

class Codec {
    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('#');
            return;
        }
        sb.append(node.val);
        write(node.left, sb);
        write(node.right, sb);
    }

    TreeNode deserialize(String data) {
        Queue<String> tokens = new ArrayDeque<>(Arrays.asList(data.split(",")));
        return read(tokens);
    }

    private TreeNode read(Queue<String> tokens) {
        String t = tokens.poll();
        if (t.equals("#")) return null;
        TreeNode node = new TreeNode(Integer.parseInt(t));
        node.left = read(tokens);
        node.right = read(tokens);
        return node;
    }
}

Python

class Codec:
    def serialize(self, root: Optional[TreeNode]) -> str:
        out = []
        self._write(root, out)
        return ",".join(out)

    def _write(self, node: Optional[TreeNode], out: List[str]) -> None:
        if not node:
            out.append("#")
            return
        out.append(str(node.val))
        self._write(node.left, out)
        self._write(node.right, out)

    def deserialize(self, data: str) -> Optional[TreeNode]:
        tokens = deque(data.split(","))
        return self._read(tokens)

    def _read(self, tokens: deque) -> Optional[TreeNode]:
        t = tokens.popleft()
        if t == "#": return None
        node = TreeNode(int(t))
        node.left = self._read(tokens)
        node.right = self._read(tokens)
        return node

C++

class Codec {
    void write(TreeNode* node, string& out) {
        if (!out.empty()) out += ',';
        if (!node) {
            out += '#';
            return;
        }
        out += to_string(node->val);
        write(node->left, out);
        write(node->right, out);
    }

    TreeNode* read(istringstream& in) {
        string t;
        getline(in, t, ',');
        if (t == "#") return nullptr;
        TreeNode* node = new TreeNode(stoi(t));
        node->left = read(in);
        node->right = read(in);
        return node;
    }

public:
    string serialize(TreeNode* root) {
        string out;
        write(root, out);
        return out;
    }

    TreeNode* deserialize(string data) {
        istringstream in(data);
        return read(in);
    }
};

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Empty tree Serializes to "#".	`root = []`	`[]`
Negative values parseInt reads the minus sign.	`root = [-1, -2]`	`[-1,-2]`
Right-skewed The # after 1 records the missing left child.	`root = [1, null, 2]`	`[1,null,2]`