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

↓

Deserialize Right

↓

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(Node root, List<string> data) {
  if (root == null) {
    data.Add("null");
    return;
  }
  data.Add(root.val.ToString());
  Serialize(root.left, data);
  Serialize(root.right, data);
}

This code serializes a binary tree into a list of strings using preorder traversal, adding "null" for empty nodes.

Execution Table

Step	Operation	Node Visited	Pointer Changes	Tree State (Visual)
1	Serialize root node	1	Add '1' to data	1 / \ 2 3
2	Serialize left child	2	Add '2' to data	1 / \ 2 3
3	Serialize left.left	null	Add 'null' to data	1 / \ 2 3
4	Serialize left.right	null	Add 'null' to data	1 / \ 2 3
5	Serialize right child	3	Add '3' to data	1 / \ 2 3
6	Serialize right.left	null	Add 'null' to data	1 / \ 2 3
7	Serialize right.right	null	Add 'null' to data	1 / \ 2 3
8	Deserialization start	Read '1'	Create node 1	1
9	Deserialize left child	Read '2'	Create node 2	1 / 2
10	Deserialize left.left	Read 'null'	Return null	1 / 2
11	Deserialize left.right	Read 'null'	Return null	1 / 2
12	Deserialize right child	Read '3'	Create node 3	1 / \ 2 3
13	Deserialize right.left	Read 'null'	Return null	1 / \ 2 3
14	Deserialize right.right	Read 'null'	Return null	1 / \ 2 3
15	Deserialization complete	Tree rebuilt	Return root node	1 / \ 2 3

💡 All nodes visited and serialized; all values read and tree rebuilt.

Variable Tracker

Variable	Start	After Step 1	After Step 5	After Step 8	After Step 15
data (serialization list)	[]	["1"]	["1","2","null","null","3"]	["1","2","null","null","3","null","null"]	["1","2","null","null","3","null","null"]
current node (serialization)	root (1)	2	3	null	null
read index (deserialization)	0	0	0	1	7
current node (deserialization)	null	1	2	3	null

Key Moments - 3 Insights

Why do we add "null" strings during serialization?

Adding "null" marks where a node is missing, so during deserialization we know when to stop and return null nodes (see steps 3,4,6,7 in execution_table).

How does deserialization know which node is left or right?

Deserialization reads values in preorder: root, left subtree, then right subtree. This order matches serialization, so recursive calls reconstruct left and right children correctly (see steps 9-14).

What happens if the tree is empty (root is null)?

Serialization immediately adds "null" and returns. Deserialization reads "null" and returns null node, resulting in an empty tree (not shown in this example but follows same logic).

Visual Quiz - 3 Questions

Look at the execution_table, what is added to data at step 5?

A "null"

B "3"

C "2"

D "1"

💡 Hint

Check the 'Operation' and 'Pointer Changes' columns at step 5 in execution_table.

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

A Step 9

B Step 14

C Step 12

D Step 15

💡 Hint

Look for 'Create node 3' in the 'Pointer Changes' column in execution_table.

If we remove adding "null" during serialization, what happens during deserialization?

A Deserialization will fail to know where to stop and may crash.

B Deserialization will work fine without changes.

C Deserialization will create extra nodes.

D Serialization will add more nodes automatically.

💡 Hint

Refer to key_moments about why "null" is added during serialization.

Concept Snapshot

Serialize: Traverse tree preorder, add node values or "null" for empty.
Deserialize: Read values preorder, create nodes or nulls recursively.
Use recursion to keep structure.
"null" marks missing children.
Preorder order keeps left/right info.
Works for any binary tree shape.

Full Transcript

Serialization of a binary tree means visiting each node in preorder (root, left, right) and recording its value. If a node is missing, we record "null" to mark that spot. This way, the entire tree structure is captured in a list of strings. Deserialization reads this list in the same order, creating nodes when it sees values and returning null when it sees "null". This recursive process rebuilds the original tree exactly. The key is that preorder traversal keeps the order of nodes so left and right children are correctly assigned. Without recording "null", deserialization would not know where children are missing and would fail. This method works for any binary tree, including empty trees.

Practice

1. What is the main purpose of serialize and deserialize methods 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 from 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: Serialization means tree to string, deserialization reverses it [OK]

Common Mistakes:

• Confusing serialization with sorting
• Thinking serialization deletes nodes
• Assuming serialization finds tree height

2. Which of the following is the correct C# method signature for a serialize method that converts a binary tree root node to a string?

easy

A. public TreeNode Serialize(string data)

B. public void Serialize(TreeNode root)

C. public string Serialize(TreeNode root)

D. public int Serialize(TreeNode root)

Solution

1. Step 1: Identify return type for serialization

   Serialization converts a tree to a string, so the return type must be string.

2. Step 2: Check method parameters

   The method should take the root node of the tree as input, typically TreeNode root.

3. Final Answer:

   public string Serialize(TreeNode root) -> Option C

4. Quick Check:

   Serialize returns string from TreeNode [OK]

Hint: Serialize returns string, input is root node [OK]

Common Mistakes:

• Using void return type for serialize
• Confusing serialize with deserialize signature
• Returning int instead of string

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

medium

A. [5, 4, 3, 2, 1]

B. [2, 1, 4, 3, 5]

C. [2, 4, 1, 3, 5]

D. [1, 2, 3, 4, 5]

Solution

1. Step 1: Reconstruct tree from preorder string

   Preorder: root=1, left subtree=2,#,# (2 with no children), right subtree=3,4,#,#,5,#,# (3 with left=4, right=5).

2. Step 2: Perform inorder traversal (left, root, right)

   Inorder: left subtree of 1 is 2, then root 1, then left subtree of 3 is 4, root 3, right subtree 5. So inorder is [2, 1, 4, 3, 5].

3. Final Answer:

   [2, 1, 4, 3, 5] -> Option B

4. Quick Check:

   Inorder matches reconstructed tree [OK]

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

Common Mistakes:

• Mixing preorder and inorder traversal orders
• Ignoring null markers '#' in deserialization
• Incorrectly assigning left and right children

4. Consider this deserialize method snippet in C#:

public TreeNode Deserialize(string data) {
  var nodes = data.Split(',');
  int index = 0;
  return DeserializeHelper(nodes, ref index);
}

private TreeNode DeserializeHelper(string[] nodes, ref int index) {
  if (index >= nodes.Length || nodes[index] == "#") {
    index++;
    return null;
  }
  TreeNode node = new TreeNode(int.Parse(nodes[index++]));
  node.left = DeserializeHelper(nodes, ref index);
  node.right = DeserializeHelper(nodes, ref index);
  return node;
}

What is the main bug if index was passed without ref keyword?

medium

A. The index will not update correctly across recursive calls, causing infinite recursion or wrong tree

B. The code will not compile due to missing ref keyword

C. The tree will deserialize correctly without any issue

D. The method will throw a NullReferenceException

Solution

1. Step 1: Understand passing index by reference

   Passing index by ref allows recursive calls to update the same variable, tracking position in the array.

2. Step 2: Effect of missing ref

   If index is passed by value, each recursive call gets a copy, so updates won't reflect outside, causing repeated processing of same nodes and infinite recursion or wrong tree.

3. Final Answer:

   The index will not update correctly across recursive calls, causing infinite recursion or wrong tree -> Option A

4. Quick Check:

   Missing ref causes index not to update globally [OK]

Hint: Pass index by ref to track position across recursion [OK]

Common Mistakes:

• Assuming code won't compile without ref
• Thinking tree deserializes correctly without ref
• Confusing NullReferenceException with index issue

5. You want to serialize a binary tree and then deserialize it back. Which approach below correctly handles trees with duplicate values and null nodes?

hard

A. Use preorder traversal with '#' for nulls and commas to separate nodes

B. Use inorder traversal without null markers

C. Use level order traversal but skip null nodes

D. Serialize only leaf nodes and ignore internal nodes

Solution

1. Step 1: Understand serialization requirements

   To handle duplicates and nulls, serialization must record node values and null positions explicitly.

2. Step 2: Evaluate options

   Preorder with '#' for nulls and commas as separators records structure and values including duplicates. Inorder without nulls loses structure. Level order skipping nulls loses position info. Serializing only leaves loses tree shape.

3. Final Answer:

   Use preorder traversal with '#' for nulls and commas to separate nodes -> Option A

4. Quick Check:

   Preorder + null markers preserves full tree [OK]

Hint: Use preorder + null markers to keep duplicates and structure [OK]

Common Mistakes:

• Skipping null nodes loses tree shape
• Using inorder without nulls loses structure
• Ignoring duplicate values in serialization