Pattern visualizer

Serialize and Deserialize Binary Tree

Preorder alone can't be reversed — [1,2,3] is ambiguous about which side 2 and 3 sit on. Writing an explicit '#' for every null child removes the ambiguity: the string tells you exactly when to stop descending, so a single preorder pass can rebuild the tree with no extra traversal needed. Animated on: Design an algorithm to convert a binary tree to a string and back, so the reconstructed tree is identical to the original, for the tree [1, 2, 3, null, null, 4, 5]..

Preorder DFS with a '#' marker for every null child

time O(n)space O(n)step 1 / 12

Call stack

serialize(1)

line 3

Visit node 1 and append it before recursing into its children (preorder). Output so far: "1".

Pseudocode

1FUNCTION serialize(node):
2  IF node = NULL: RETURN "#"
3  RETURN node.val + "," + serialize(node.left) + "," + serialize(node.right)
4END FUNCTION
5FUNCTION deserialize(tokens):
6  token <- NEXT(tokens)
7  IF token = "#": RETURN NULL
8  node <- NEW NODE(token)
9  node.left <- deserialize(tokens)
10  node.right <- deserialize(tokens)
11  RETURN node
12END FUNCTION

← / → step · space play · Home restart

Where to practice Binary Trees

Practice Binary Trees problems All Binary Trees problems Back to roadmap