Serialize And Deserialize Binary Tree

HARD✓ CHIP-TIMEDLC #297 — FULL STATEMENT ↗

The drill: Turn a binary tree into one string and turn that string back into the exact same tree — same shape, same null placement, same values — with no shared object between the two sides, only the text.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A binary tree needs to become a single string and then turn back into a tree from nothing but that string — no shared references between the writing side and the reading side, only the text passes between them.

The rebuilt tree has to match the original exactly: same shape, same values, same nulls in the same places, since a wrong reconstruction can't be told apart from a right one without checking every branch.

This site checks the drill as one round trip — your function takes a tree, encodes and decodes it internally however you like, and the judge compares the tree that comes back out against the one that went in.

EX 01

root = [7]

→ [7]

SINGLE NODE

EX 02

root = []

→ []

EMPTY TREE

EX 03

root = [0]

→ [0]

SINGLE NODE VALUED ZERO

tree sizes run up to a few thousand nodes
values can be negative, zero, or positive
null children must round-trip correctly, not just present ones
the judge compares the rebuilt tree structurally to the original

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A tree can't cross a wire as pointers — it has to flatten into a sequence of tokens first, and that sequence has to carry enough information to rebuild every branch, including the ones that don't exist.

HINT 2 THE STRUCTURE

A fixed traversal order plus an explicit marker for “no child here” is enough — the reader just needs to know, at every step, whether the next token opens a subtree or closes one early.

HINT 3 ONE STEP FROM THE ANSWER

Preorder: write the value, then recurse left, then right, writing a marker in place of every null. Decoding replays the same order — pull one token at a time and it tells you whether to build a node or stop.

COACH'S BOARD — THE PATTERN, STEP BY STEP

MARKERS FOR NOTHINGPATTERN · PREORDER WITH MARKERSroot = [5, 3, 8]

QUEUE

— empty —

STEP 1

Serialize with preorder: write a node's value, then recurse left, then right — write # for every missing child so nulls survive the trip.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/serialize-and-deserialize-binary-tree.py — RACE PACE

LANG ▸

PACE ▸

class Codec:
    def serialize(self, root: Optional[TreeNode]) -> str:
        vals = []

        def dfs(node):
            if node is None:
                vals.append("#")
                return
            vals.append(str(node.val))
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return ",".join(vals)

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

        def build():
            val = next(tokens)
            if val == "#":
                return None
            node = TreeNode(int(val))
            node.left = build()
            node.right = build()
            return node

        return build()


class Solution:
    def roundTrip(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        codec = Codec()
        return codec.deserialize(codec.serialize(root))

TIME O(N)SPACE O(N)PYTHON · RACE PACE · 34 LN

class Codec:
    def serialize(self, root: Optional[TreeNode]) -> str:
        if root is None:
            return "#"
        vals = []
        queue = collections.deque([root])
        while queue:
            node = queue.popleft()
            if node is None:
                vals.append("#")
                continue
            vals.append(str(node.val))
            queue.append(node.left)
            queue.append(node.right)
        return ",".join(vals)

    def deserialize(self, data: str) -> Optional[TreeNode]:
        tokens = data.split(",")
        if tokens[0] == "#":
            return None
        root = TreeNode(int(tokens[0]))
        queue = collections.deque([root])
        i = 1
        while queue:
            node = queue.popleft()
            left_val = tokens[i]
            i += 1
            if left_val != "#":
                node.left = TreeNode(int(left_val))
                queue.append(node.left)
            right_val = tokens[i]
            i += 1
            if right_val != "#":
                node.right = TreeNode(int(right_val))
                queue.append(node.right)
        return root


class Solution:
    def roundTrip(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        codec = Codec()
        return codec.deserialize(codec.serialize(root))

TIME O(N)SPACE O(N)PYTHON · TRAINING PACE · 42 LN

class Codec {
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serializeHelper(root, sb);
        return sb.toString();
    }

    private void serializeHelper(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append("#,");
            return;
        }
        sb.append(node.val).append(",");
        serializeHelper(node.left, sb);
        serializeHelper(node.right, sb);
    }

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

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

class Solution {
    public TreeNode roundTrip(TreeNode root) {
        Codec codec = new Codec();
        return codec.deserialize(codec.serialize(root));
    }
}

TIME O(N)SPACE O(N)JAVA · RACE PACE · 38 LN

class Codec {
    public String serialize(TreeNode root) {
        if (root == null) return "#";
        StringBuilder sb = new StringBuilder();
        // LinkedList, not ArrayDeque: the queue carries null child markers
        Deque<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                sb.append("#,");
                continue;
            }
            sb.append(node.val).append(",");
            queue.add(node.left);
            queue.add(node.right);
        }
        return sb.toString();
    }

    public TreeNode deserialize(String data) {
        String[] tokens = data.split(",");
        if (tokens[0].equals("#")) return null;
        TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            String leftVal = tokens[i++];
            if (!leftVal.equals("#")) {
                node.left = new TreeNode(Integer.parseInt(leftVal));
                queue.add(node.left);
            }
            String rightVal = tokens[i++];
            if (!rightVal.equals("#")) {
                node.right = new TreeNode(Integer.parseInt(rightVal));
                queue.add(node.right);
            }
        }
        return root;
    }
}

class Solution {
    public TreeNode roundTrip(TreeNode root) {
        Codec codec = new Codec();
        return codec.deserialize(codec.serialize(root));
    }
}

TIME O(N)SPACE O(N)JAVA · TRAINING PACE · 50 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED