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.

Practice

1. What is the main purpose of serialize and deserialize functions in the context of a binary tree?

easy

A. Find the height of the binary tree

B. Sort the binary tree nodes in ascending order

C. Delete all nodes of the binary tree

D. Convert a binary tree to a string and back to a binary tree

Solution

1. Step 1: Understand serialization

   Serialization means converting a data structure like a binary tree into a string format that can be stored or transmitted.

2. Step 2: Understand deserialization

   Deserialization means converting the string back into the original binary tree structure.

3. Final Answer:

   Convert a binary tree to a string and back to a binary tree -> Option D

4. Quick Check:

   Serialize/Deserialize = Convert tree to/from string [OK]

Hint: Think of serialize as packing, deserialize as unpacking [OK]

Common Mistakes:

• Confusing serialization with sorting
• Thinking it deletes nodes
• Assuming it calculates tree height

2. Which of the following is a correct way to represent a null node during serialization of a binary tree in C++ using a single-character marker?

easy

A. "null"

B. "#"

C. 0

D. -1

Solution

1. Step 1: Identify common null markers

   In many serialization methods, a special character like '#' is used to mark null nodes to distinguish them from valid node values.

2. Step 2: Compare options

   "null" is a string but longer and less common; 0 and -1 can be valid node values, so they are ambiguous.

3. Final Answer:

   "#" -> Option B

4. Quick Check:

   Null node marker = "#" [OK]

Hint: Use a unique symbol like '#' for null nodes [OK]

Common Mistakes:

• Using 0 or -1 which can be valid node values
• Using the word "null" which is verbose
• Not marking null nodes at all

3. Given the following serialized string of a binary tree using preorder traversal with '#' as null marker: "1 2 # # 3 4 # # 5 # #", what is the inorder traversal of the tree?

medium

A. 2 1 4 3 5

B. 1 2 3 4 5

C. 2 4 1 5 3

D. 3 2 1 5 4

Solution

1. Step 1: Reconstruct the tree from preorder

   Preorder: 1 (root), 2 (left child), # (left null), # (right null), 3 (right child), 4 (left child), #, #, 5 (right child), #, #.

2. Step 2: Draw the tree and find inorder

   Tree structure:
       1
     /     \
    2        3
             /  \
           4      5
   Inorder (left, root, right): 2 1 4 3 5

3. Final Answer:

   2 1 4 3 5 -> Option A

4. Quick Check:

   Inorder from tree = 2 1 4 3 5 [OK]

Hint: Draw tree from preorder, then do inorder traversal [OK]

Common Mistakes:

• Mixing preorder and inorder sequences
• Ignoring null markers
• Incorrect tree reconstruction

4. Consider this C++ snippet for deserializing a binary tree from a vector of strings representing preorder traversal with '#' as null marker:

TreeNode* deserializeHelper(vector<string>& data, int& index) {
  if (index >= data.size() || data[index] == "#") {
    index++;
    return nullptr;
  }
  TreeNode* node = new TreeNode(stoi(data[index++]));
  node->left = deserializeHelper(data, index);
  node->right = deserializeHelper(data, index);
  return node;
}

What is the bug in this code?

medium

A. The stoi conversion can throw exception without try-catch

B. The index is incremented twice for null nodes causing skipping elements

C. The function does not handle empty input vector

D. The function does not assign right child correctly

Solution

1. Step 1: Identify the stoi vulnerability

   The code uses stoi(data[index++]) without validating that data[index] is a valid integer string. Malformed input (non-numeric other than '#') causes unhandled std::invalid_argument exception.

2. Step 2: Rule out other options

   Index increments once per token: for '#' via index++ in if; for values via index++ in stoi. Empty input handled by index >= data.size(). Right child assigned correctly.

3. Final Answer:

   The stoi conversion can throw exception without try-catch -> Option A

4. Quick Check:

   stoi requires valid numeric strings [OK]

Hint: Validate inputs before stoi to prevent exceptions [OK]

Common Mistakes:

• Assuming no index increment for null nodes
• Ignoring possible exceptions from stoi
• Thinking right child assignment is missing

5. You want to serialize a binary tree and then deserialize it back. However, your tree contains integer node values that can be negative, zero, or positive. Which approach ensures correct serialization and deserialization without ambiguity?

hard

A. Serialize only node values ignoring nulls, reconstruct tree by sorting

B. Use comma-separated values but skip null markers to reduce size

C. Use space-separated values with '#' for nulls and convert strings to int using stoi

D. Serialize using preorder but replace negative values with zero

Solution

1. Step 1: Consider node values including negatives and zero

   Using space-separated values with '#' for nulls preserves structure and allows negative values as strings can represent negatives.

2. Step 2: Evaluate other options

   Use comma-separated values but skip null markers to reduce size skips nulls, losing tree shape.
   Serialize only node values ignoring nulls, reconstruct tree by sorting ignores nulls and sorts, losing original structure.
   Serialize using preorder but replace negative values with zero replaces negatives with zero, losing data.

3. Final Answer:

   Use space-separated values with '#' for nulls and convert strings to int using stoi -> Option C

4. Quick Check:

   Preserve nulls and convert strings properly [OK]

Hint: Keep null markers and convert strings carefully [OK]

Common Mistakes:

• Skipping null markers losing tree shape
• Replacing negative values losing data
• Sorting nodes losing original tree