Serialize and Deserialize Binary Tree in DSA C++ - Execution Trace

Concept Flow - Serialize and Deserialize Binary Tree

Start Serialization

↓

Visit Node

↓

Serialize Left

↓

Add Node Value or Null

↓

End Serialization

↓

Start Deserialization

↓

Read Next Value

↓

Return Null

↓

Deserialize Left

↓

Return Node

↓

End Deserialization

Serialization visits nodes in preorder, recording values or nulls; deserialization reads values to rebuild the tree recursively.

Execution Sample

DSA C++

void serialize(TreeNode* root, string& out) {
  if (!root) { out += "#,"; return; }
  out += to_string(root->val) + ",";
  serialize(root->left, out);
  serialize(root->right, out);
}

TreeNode* deserialize(istringstream& in) {
  string val;
  getline(in, val, ',');
  if (val == "#") return nullptr;
  TreeNode* node = new TreeNode(stoi(val));
  node->left = deserialize(in);
  node->right = deserialize(in);
  return node;
}

This code serializes a binary tree into a string with preorder traversal and '#' for nulls, then deserializes it back.

Execution Table

Step	Operation	Node Visited	Pointer Changes	Tree State (Preorder)
1	Serialize root	1	out += '1,'	1
2	Serialize left child	2	out += '2,'	1 -> 2
3	Serialize left.left (null)	null	out += '#,'	1 -> 2 -> #
4	Serialize left.right (null)	null	out += '#,'	1 -> 2 -> # -> #
5	Serialize right child	3	out += '3,'	1 -> 2 -> # -> # -> 3
6	Serialize right.left (null)	null	out += '#,'	1 -> 2 -> # -> # -> 3 -> #
7	Serialize right.right (null)	null	out += '#,'	1 -> 2 -> # -> # -> 3 -> # -> #
8	Serialization complete	N/A	out = '1,2,#,#,3,#,#,'	Full serialized string
9	Deserialize root	1	Create node 1	1
10	Deserialize left child	2	Create node 2	1 -> 2
11	Deserialize left.left	null	Return null	1 -> 2 -> null
12	Deserialize left.right	null	Return null	1 -> 2 -> null -> null
13	Deserialize right child	3	Create node 3	1 -> 2 -> null -> null -> 3
14	Deserialize right.left	null	Return null	1 -> 2 -> null -> null -> 3 -> null
15	Deserialize right.right	null	Return null	1 -> 2 -> null -> null -> 3 -> null -> null
16	Deserialization complete	N/A	Tree rebuilt	Tree structure restored

💡 All nodes visited and serialized/deserialized; nulls marked with '#' to preserve structure.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 5	After Step 8	After Step 9	After Step 16
out (string)	""	"1,"	"1,2,"	"1,2,#,#,3,"	"1,2,#,#,3,#,#,"	"1,2,#,#,3,#,#,"	"1,2,#,#,3,#,#,"
current node (serialize)	root (1)	2	null	3	null	N/A	N/A
input stream (deserialize)	empty	reading '1'	reading '2'	reading '3'	reading '#'	reading '#'	end
current node (deserialize)	null	node 1 created	node 2 created	node 3 created	null	null	tree root

Key Moments - 3 Insights

Why do we add '#' for null nodes during serialization?

Adding '#' marks where a node is missing, so during deserialization we know exactly where to place nulls, preserving tree shape (see execution_table rows 3,4,6,7).

How does deserialization know when to stop reading children?

When it reads '#', it returns null immediately, stopping further recursion for that branch (see execution_table rows 11,12,14,15).

Why is preorder traversal used for serialization?

Preorder visits root before children, so the first value is always the root, making it easy to reconstruct the tree recursively (see execution_table steps 1,9).

Visual Quiz - 3 Questions

Look at the execution_table, what is the serialized string after step 8?

A "1,2,#,#,3,#,#,"

B "1,2,3,#,#,#,#,"

C "1,#,2,#,3,#,#,"

D "#,#,1,2,3,#,#,"

💡 Hint

Check the 'out' variable in variable_tracker after step 8.

At which step does deserialization create the right child node with value 3?

A Step 15

B Step 10

C Step 13

D Step 9

💡 Hint

Look at execution_table rows describing deserialization node creation.

If we remove '#' for null nodes during serialization, what happens during deserialization?

A Deserialization runs faster

B Tree structure cannot be correctly rebuilt

C No change in tree structure

D Deserialization creates extra nodes

💡 Hint

Refer to key_moments about why '#' is needed for null nodes.

Concept Snapshot

Serialize and Deserialize Binary Tree:
- Serialize with preorder traversal
- Use '#' to mark null nodes
- Store values separated by commas
- Deserialize by reading values recursively
- '#' means return null node
- Preserves exact tree structure

Full Transcript

Serialization of a binary tree uses preorder traversal to visit nodes. Each node's value is added to a string, separated by commas. Null children are marked with '#'. This string fully represents the tree structure. Deserialization reads this string token by token. When it reads a value, it creates a node; when it reads '#', it returns null. This recursive process rebuilds the original tree exactly. The key is marking nulls to preserve shape. Preorder ensures root is first, simplifying reconstruction.