← DSA Atlas
Dedicated problem page · #297

Serialize and Deserialize Binary Tree

HardTrees and Binary Search TreesPre-order encode with null markersDFS serialization / recursive reconstruction
Solve on LeetCode ↗
297
HardTrees and Binary Search TreesDFS serialization / recursive reconstructionPre-order encode with null markers

Serialize and Deserialize Binary Tree

Design an algorithm to serialize a binary tree to a single string and deserialize that string back into the identical tree structure. You implement two methods, serialize and deserialize, and the round trip must reproduce the original tree.

Open official problem prompt ↗
In plain English

Convert a binary tree into a reversible string and reconstruct the exact same tree from that string, preserving both values and structure.

Picture it like this

Think of dictating a family tree over the phone. If you only read names you lose who is missing; but if you also say 'no child here' at every gap, the listener can redraw the tree exactly. The '#' marker is that spoken 'no child here'.

Example
Input
root = [1, 2, 3, null, null, 4, 5]
Output
[1, 2, 3, null, null, 4, 5]
Why
serialize produces a string encoding the tree, and deserialize rebuilds the exact same tree, so the round trip returns the original.
Constraints
The number of nodes is in the range [0, 10^4]-1000 <= Node.val <= 1000
Pattern lesson

See the pattern, then code

Pre-order encode with null markers
Recognition clue

You must fully capture tree shape AND values in a flat string and rebuild unambiguously — the classic fix is to emit explicit null markers so structure is never guessed.

↗
Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. A pre-order walk that writes a sentinel for every missing child makes the sequence uniquely decodable: reading the same pre-order stream lets a recursive builder consume values in exactly the order they were written.

New words, made simpleKnow these before the algorithm
Serialize
Turn an in-memory structure into a flat, storable/transmittable string.
Sentinel / null marker
A special token ('#') standing in for a missing child so structure is explicit.
Iterator
A cursor over the token list that yields the next token on demand, keeping recursion in sync.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Values only, no markers

Ambiguous — a single pre-order (or in-order) of values alone cannot reconstruct a unique tree.

Write a traversal of values without recording nulls.

Time O(n)Space O(n)
Best choicePre-order with null sentinels

Uniquely decodable and simple recursion in both directions.

Emit each value and a '#' for every empty child; rebuild by consuming tokens in the same order.

Time O(n)Space O(n)
The rule we keep true

Invariant

During deserialize, build() consumes exactly the tokens that serialize's dfs wrote for the same subtree, in the same order, so the cursor is always positioned at the next unread node.

Why this is correct

Reasoning

Pre-order writes node, then its entire left subtree, then its entire right subtree, and includes '#' for absent children. Reconstruction mirrors that contract: read a token, if it's a value create the node and recursively build its left subtree (which will consume exactly its tokens) then its right. Because every position is explicitly marked, there is exactly one tree consistent with the stream.

The algorithm in three movesSay these aloud before coding
1Serialize: pre-order DFS, append each value, append '#' for null children

serialize -> '1,2,#,#,3,4,#,#,5,#,#'

2Join tokens into a comma-separated string

deserialize reads 1 -> node(1)

3Deserialize: split into tokens and read them with an iterator

next tokens build left=2, right=3 subtree

4Rebuild recursively — '#' becomes None, otherwise create a node and build its left then right

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
21
#2
#3
34
45
1 · Readnode 1
2 · Askemit?
3 · Update stateout=['1']
4 · Resultrecurse left (2)
Key takeaway

Pre-order tokens with '#' sentinels encode both values and the missing children.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 5-11Pre-order emit

    Append the value, then recurse left and right; nulls become '#' so gaps are explicit.

  2. 2
    Lines 13Flatten

    Join tokens with commas into one transmittable string.

  3. 3
    Lines 16Token iterator

    An iterator lets recursive calls each pull the next token without index bookkeeping.

  4. 4
    Lines 18-25Recursive rebuild

    '#' returns None; otherwise create the node and build left then right in the same pre-order the writer used.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Empty tree (root is None) serializes to '#' and deserializes back to None
  • Single node tree
  • Negative values — int() parses the leading minus correctly
  • Skewed tree — deep recursion of depth O(h)
!

Common beginner mistakes

  • Omitting null markers, making the string ambiguous
  • Using in-order traversal, which is not uniquely decodable on its own
  • Splitting values without a consistent delimiter so multi-digit or negative numbers merge
  • Advancing the token cursor for left and right subtrees in the wrong order
Check your understanding

Why does pre-order with null markers reconstruct a unique tree while pre-order of values alone does not?

More in Trees and Binary Search Trees

#104Maximum Depth of Binary TreePost-order height aggregation#543Diameter of Binary TreePost-order height with a running best#102Binary Tree Level Order TraversalLevel-by-level BFS#98Validate Binary Search TreeRange-bounded validation#236Lowest Common Ancestor of a Binary TreeBottom-up LCA search#105Construct Binary Tree from Preorder and InorderPreorder root + inorder split