LeetCode 297 · Hard · Trees

Serialize and Deserialize Binary Tree

Design two functions: one turns a binary tree into a string, the other turns that string back into the very same tree. Any format works as long as the round trip is exact.

O(n)time, both ways
O(n)space · the string
preorder + "N"null markers fix the shape

level order as on LeetCode, null = no child · up to 15 nodes, 4 levels · values −99 to 99

Original

Rebuilt from the string alone

tokens res while serializing · vals while deserializing · i = next token to read

i

data the string itself

Call stack one frame per dfs call · newest on the right

public class Codec { private String[] vals; private int i; public String serialize(TreeNode root) { List<String> res = new ArrayList<>(); dfs(root, res); return String.join(",", res); } private void dfs(TreeNode node, List<String> res) { if (node == null) { res.add("N"); return; } res.add(String.valueOf(node.val)); dfs(node.left, res); dfs(node.right, res); } public TreeNode deserialize(String data) { vals = data.split(","); i = 0; return dfs(); } private TreeNode dfs() { if (vals[i].equals("N")) { i++; return null; } TreeNode node = new TreeNode(Integer.parseInt(vals[i])); i++; node.left = dfs(); node.right = dfs(); return node; }}
phase
—
node
—
tokens
0
i
—

Why it works

  1. Values alone are not enough. A plain preorder list of values cannot tell [1,2] from [1,null,2]; you would need a second traversal (preorder + inorder, problem 105) and distinct values.
  2. Write every null as "N". With the null markers, preorder pins the tree down: the reader meets each token in the same order the writer produced it, so one recursive reader with a shared index i rebuilds node, left subtree, right subtree, exactly mirroring the writer.
  3. Cost: a tree with n nodes has n + 1 null children, so the string holds 2n + 1 tokens. Both directions touch each token once: O(n) time, O(n) space for the string, O(h) for the call stack.
  4. Pitfall: splitting on single characters. Values like -12 or 45 span several characters, so the tokens need a separator (the comma) and Integer.parseInt on each piece.
  5. Alternative: BFS level order with "N" markers works too (it is LeetCode's own format); the reader then attaches children from a queue instead of recursing.