DSA Tracker

Visualize

Serialize and Deserialize Binary Tree

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

time O(n)space O(n)

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.

Details

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].

Problem:Serialize and Deserialize Binary TreeHard

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

step 1 / 12

2
1
4
3
5

Call stack

serialize(1)

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

Every step in words

Show all 12 steps
  1. Visit node 1 and append it before recursing into its children (preorder). Output so far: "1".
  2. Node 2 has no children, so append '2' then '#,#' for its null left and right. Output so far: "1,2,#,#".
  3. Visit node 3 and append it before recursing into its children (preorder). Output so far: "1,2,#,#,3".
  4. Node 4 has no children, so append '4' then '#,#' for its null left and right. Output so far: "1,2,#,#,3,4,#,#".
  5. Node 5 has no children, so append '5' then '#,#' for its null left and right. Output so far: "1,2,#,#,3,4,#,#,5,#,#".
  6. Preorder DFS finished. Every null child left a '#' marker, so the string is self-delimiting: "1,2,#,#,3,4,#,#,5,#,#".
  7. Read token '1': create node 1 and attach it as the new root.
  8. Read token '2': create node 2 and attach it as left child of 1.
  9. Read token '3': create node 3 and attach it as right child of 1.
  10. Read token '4': create node 4 and attach it as left child of 3.
  11. Read token '5': create node 5 and attach it as right child of 3.
  12. All tokens consumed and every node reattached in the same order they were written — the reconstructed tree matches the original.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Serialize and Deserialize Binary Tree in the editorAll Binary Trees problemsBack to roadmap