progress

~/problems / Trees / Binary trees

Serialize and Deserialize Binary Tree

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

hard ~30 min

TreeNode(val, left=None, right=None) is in the starter. Keep it.

Implement a class Codec with two methods:

  • serialize(root) -> str: encode a binary tree (or None) as a string.
  • deserialize(data) -> TreeNode | None: rebuild the tree from such a string.

You choose the format. The only requirement is that Codec().deserialize(Codec().serialize(t)) rebuilds a tree with the same shape and the same values as t, using a separate Codec instance for each step. So the string must carry all the information; nothing can be stashed on the object.

Values are integers, possibly negative or several digits long, and may repeat.

#      1
#     / \
#    2   3
#       / \
#     -40  5
s = Codec().serialize(root)        # e.g. "1,2,3,#,#,-40,5,#,#,#,#"
t = Codec().deserialize(s)         # a new tree shaped exactly like root

Trees can have up to 10,000 nodes.

⭐ Bonus: a speed test with a 3,000-level path and a 10,000-node tree earns a star if both methods are O(n) and walk the tree iteratively (recursion that deep hits Python's limit).

Show hint

Write the values in a fixed traversal order, with a marker wherever a child is missing; the markers are what make the shape recoverable. Level order (with a queue) is the easiest to read back without recursion.

Topic: Binary trees. Recursive return values (height, best path), BFS by level, BST invariants.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc