Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Serialize and Deserialize Binary Tree

LeetCode #297Hard
Pre-order with null markers, then rebuild from the stream

Design an algorithm to serialize a binary tree to a string and deserialize that string back into the identical tree. There is no restriction on the encoding/decoding format.

Asked atAmazonMetaLinkedInGoogle
step 1 / 27
binary tree
2
1
4
3
5
call stack ↓
(returned)
Serialize · pre-order with null markers
▸
1serialize(node):
2    if node: append(node.val)         // record on arrival (pre-order)
3    else:    append("#"); return      // null marker keeps it unambiguous
4    serialize(node.left); serialize(node.right)
5// result = "1,2,#,#,3,4,#,#,5,#,#"
state
  • orderpre-order: node, L, R
  • serialized∅

line 1Serializing turns a tree into a flat string we can store or send. We walk PRE-ORDER (node, then left, then right) and write each value as we arrive. The trick that makes the string UNAMBIGUOUS: whenever a child is missing we still write a "#" marker. Without those null markers, "1,2,3" could rebuild into many different shapes — the #s pin down exactly where each subtree stops.