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

↓

Repeat for all nodes

↓

End Serialization

↓

Start Deserialization

↓

Read Next Value

↓

If Null -> return None

↓

Create Node

↓

Deserialize Left

↓

Repeat for all values

↓

End Deserialization

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

Execution Sample

DSA C

void serialize(Node* root, FILE* out) {
  if (!root) { fprintf(out, "# "); return; }
  fprintf(out, "%d ", root->val);
  serialize(root->left, out);
  serialize(root->right, out);
}

Node* deserialize(FILE* in) {
  char val[10];
  if (!fscanf(in, "%s", val) || val[0] == '#') return NULL;
  Node* node = (Node*)malloc(sizeof(Node));
  node->val = atoi(val);
  node->left = deserialize(in);
  node->right = deserialize(in);
  return node;
}

This code writes node values or '#' for nulls in preorder, then reads them back to rebuild the tree.

Execution Table

Step	Operation	Node Visited / Value Read	Pointer Changes	Tree State (Preorder)
1	Serialize root	Node 1	None	1
2	Serialize left child	Node 2	None	1 -> 2
3	Serialize left of Node 2	NULL	None	1 -> 2 -> #
4	Serialize right of Node 2	NULL	None	1 -> 2 -> # -> #
5	Serialize right child	Node 3	None	1 -> 2 -> # -> # -> 3
6	Serialize left of Node 3	Node 4	None	1 -> 2 -> # -> # -> 3 -> 4
7	Serialize left of Node 4	NULL	None	1 -> 2 -> # -> # -> 3 -> 4 -> #
8	Serialize right of Node 4	NULL	None	1 -> 2 -> # -> # -> 3 -> 4 -> # -> #
9	Serialize right of Node 3	Node 5	None	1 -> 2 -> # -> # -> 3 -> 4 -> # -> # -> 5
10	Serialize left of Node 5	NULL	None	1 -> 2 -> # -> # -> 3 -> 4 -> # -> # -> 5 -> #
11	Serialize right of Node 5	NULL	None	1 -> 2 -> # -> # -> 3 -> 4 -> # -> # -> 5 -> # -> #
12	Deserialize root	Read 1	Create Node 1	1
13	Deserialize left child	Read 2	Create Node 2	1 -> 2
14	Deserialize left of Node 2	Read #	NULL	1 -> 2 -> #
15	Deserialize right of Node 2	Read #	NULL	1 -> 2 -> # -> #
16	Deserialize right child	Read 3	Create Node 3	1 -> 2 -> # -> # -> 3
17	Deserialize left of Node 3	Read 4	Create Node 4	1 -> 2 -> # -> # -> 3 -> 4
18	Deserialize left of Node 4	Read #	NULL	1 -> 2 -> # -> # -> 3 -> 4 -> #
19	Deserialize right of Node 4	Read #	NULL	1 -> 2 -> # -> # -> 3 -> 4 -> # -> #
20	Deserialize right of Node 3	Read 5	Create Node 5	1 -> 2 -> # -> # -> 3 -> 4 -> # -> # -> 5
21	Deserialize left of Node 5	Read #	NULL	1 -> 2 -> # -> # -> 3 -> 4 -> # -> # -> 5 -> #
22	Deserialize right of Node 5	Read #	NULL	1 -> 2 -> # -> # -> 3 -> 4 -> # -> # -> 5 -> # -> #
23	End	All nodes processed	Tree rebuilt	Tree fully reconstructed
24	Exit	No more values	Stop recursion	Deserialization complete

💡 All nodes visited and nulls processed; serialization and deserialization complete.

Variable Tracker

Variable	Start	After Step 1	After Step 5	After Step 11	After Step 12	After Step 18	After Step 23
Current Node (Serialize)	root (1)	2	3	5	-	-	-
Serialized Output	""	"1 "	"1 2 # # 3 "	"1 2 # # 3 4 # # 5 # # "	"1 2 # # 3 4 # # 5 # # "	-	-
Current Node (Deserialize)	-	-	-	-	1	4	-
Deserialized Tree Size	0	0	0	0	1	4	5

Key Moments - 3 Insights

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

Because without '#' placeholders, we cannot tell if a child is missing or if the tree ended; see execution_table rows 3,4,7,8 where '#' marks null children.

Why does deserialization read values in the same order as serialization?

Because deserialization uses preorder reading to match the serialization order, ensuring nodes and nulls are reconstructed correctly; see execution_table rows 12-22.

What happens if we miss a '#' during serialization?

The deserialization will misinterpret the tree structure, causing wrong node connections or crashes; the '#' ensures tree shape is preserved as shown in serialization steps 3-4 and 7-8.

Visual Quiz - 3 Questions

Look at the execution_table, what is the serialized output after step 11?

A "1 2 # # 3 4 # # 5 # # "

B "1 2 3 4 5"

C "1 # 2 # 3 # 4 # 5"

D "# # # # #"

💡 Hint

Check the 'Serialized Output' variable in variable_tracker after step 11.

At which step does deserialization create the node with value 4?

A Step 14

B Step 17

C Step 20

D Step 22

💡 Hint

Look at execution_table row 17 where 'Create Node 4' happens.

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

A Deserialization will correctly rebuild the tree.

B Deserialization will stop early without errors.

C Deserialization will misinterpret tree structure causing errors.

D Deserialization will create extra nodes.

💡 Hint

Refer to key_moments explaining the importance of '#' placeholders.

Concept Snapshot

Serialize: preorder traverse tree, write node values or '#' for nulls.
Deserialize: read values preorder, create nodes or return null for '#'.
'#' marks null children to preserve tree shape.
Both use recursion to process left and right subtrees.
Serialization output is a string representing tree structure.
Deserialization rebuilds tree exactly from this string.

Full Transcript

Serialization and deserialization of a binary tree use preorder traversal. Serialization writes each node's value followed by its left and right children recursively. Null children are marked with '#'. Deserialization reads this sequence, creating nodes or returning null when '#' is read, reconstructing the original tree structure. This process ensures the tree can be saved and restored exactly. The execution table shows each step visiting nodes and writing or reading values, while the variable tracker follows the current node and output string. Key moments clarify why '#' is essential and why preorder order must match. The visual quiz tests understanding of serialized output, node creation steps, and the role of null markers.

Practice

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

easy

A. Delete all nodes in the binary tree

B. Sort the binary tree nodes in ascending order

C. Find the height 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 binary tree into a string format so it can be stored or sent easily.

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 string and back [OK]

Hint: Serialization means tree to string, deserialization reverses it [OK]

Common Mistakes:

• Thinking serialization sorts nodes
• Confusing serialization with deletion
• Believing serialization finds tree height

2. Which of the following is the correct way to represent a null node during serialization of a binary tree in C?

easy

A. "null"

B. "#"

C. "0"

D. "-1"

Solution

1. Step 1: Identify common null markers

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

2. Step 2: Compare options

   "null" is a string but longer; "0" and "-1" can be valid node values, so "#" is safest and most common.

3. Final Answer:

   "#" -> Option B

4. Quick Check:

   Null node marker = "#" [OK]

Hint: Use '#' to mark null nodes in serialization [OK]

Common Mistakes:

• Using '0' which can be a valid node value
• Using 'null' string which is verbose
• Using '-1' which might be a valid value

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

medium

A. 1 2 3 4 5

B. 2 4 1 3 5

C. 2 1 4 3 5

D. 4 2 5 3 1

Solution

1. Step 1: Reconstruct the tree from preorder

   Preorder: root, left, right. The string means:
   Root=1
   Left subtree: 2, #, # (2 with no children)
   Right subtree: 3,4,#,#,5,#,# (3 with left=4 no children, right=5 no children)

2. Step 2: Find inorder traversal

   Inorder: left, root, right
   Left subtree inorder: 2
   Root: 1
   Right subtree inorder: left(4), root(3), right(5) -> 4 3 5
   Combine: 2 1 4 3 5

3. Final Answer:

   2 1 4 3 5 -> Option C

4. Quick Check:

   Preorder to inorder conversion = 2 1 4 3 5 [OK]

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

Common Mistakes:

• Mixing preorder and inorder orders
• Ignoring null markers and misbuilding tree
• Swapping left and right children

4. Consider this buggy C code snippet for deserializing a binary tree node from a string token:

if (strcmp(token, "#") == 0) {
    return NULL;
}
node = malloc(sizeof(TreeNode));
node->val = atoi(token);
node->left = deserialize(tokens);
node->right = deserialize(tokens);
return node;

What is the main issue causing incorrect deserialization?

medium

A. Not advancing the token pointer before recursive calls

B. Using atoi instead of strtol for conversion

C. Not checking if malloc returns NULL

D. Comparing token with "#" incorrectly

Solution

1. Step 1: Understand token usage

   Deserialization uses tokens from a list or array. Each recursive call must move to the next token to read the next node.

2. Step 2: Identify missing token advancement

   The code does not advance the token pointer before calling deserialize recursively, so it reads the same token repeatedly causing infinite recursion or wrong tree.

3. Final Answer:

   Not advancing the token pointer before recursive calls -> Option A

4. Quick Check:

   Advance token pointer before recursion [OK]

Hint: Always move to next token before recursive deserialize calls [OK]

Common Mistakes:

• Ignoring token pointer movement
• Focusing on atoi vs strtol which is less critical here
• Missing malloc NULL check but not main bug

5. You want to serialize a binary tree and then deserialize it back. Which approach ensures the tree structure is preserved even if node values contain commas or special characters?

hard

A. Use level-order traversal with a delimiter and escape special characters in node values

B. Use preorder traversal with commas and '#' for nulls without escaping

C. Serialize only node values ignoring nulls

D. Store tree as an array without any delimiter

Solution

1. Step 1: Understand problem with special characters

   If node values contain commas or special symbols, simple comma separation breaks parsing because commas appear inside values.

2. Step 2: Use level-order with escaping

   Level-order traversal with a delimiter and escaping special characters ensures each node value is correctly separated and nulls are marked, preserving structure.

3. Step 3: Why other options fail

   Use preorder traversal with commas and '#' for nulls without escaping fails because no escaping means parsing errors. Serialize only node values ignoring nulls loses structure by ignoring nulls. Store tree as an array without any delimiter without delimiter cannot separate nodes.

4. Final Answer:

   Use level-order traversal with a delimiter and escape special characters in node values -> Option A

5. Quick Check:

   Escape special chars + delimiter + level-order = safe serialization [OK]

Hint: Escape special chars and use delimiter in level-order serialization [OK]

Common Mistakes:

• Ignoring special characters in node values
• Not escaping delimiters causing parse errors
• Skipping null nodes losing tree shape