Serialize and Deserialize Binary Tree in DSA Java - Execution Trace

Concept Flow - Serialize and Deserialize Binary Tree

Start Serialization

↓

Visit Node

↓

Left Subtree

↓

Serialize Left

↓

Combine Results

↓

End Serialization

↓

Start Deserialization

↓

Read Next Value

↓

Create Node or Null

↓

Deserialize Left

↓

Combine Subtrees

↓

End Deserialization

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

Execution Sample

DSA Java

class TreeNode {
  int val;
  TreeNode left, right;
  TreeNode(int v) { val = v; }
}

String serialize(TreeNode root) {
  if (root == null) return "#";
  return root.val + "," + serialize(root.left) + "," + serialize(root.right);
}

TreeNode deserialize(Queue<String> nodes) {
  String val = nodes.poll();
  if (val.equals("#")) return null;
  TreeNode node = new TreeNode(Integer.parseInt(val));
  node.left = deserialize(nodes);
  node.right = deserialize(nodes);
  return node;
}

This code converts a binary tree to a string using preorder traversal with '#' for nulls, then rebuilds the tree from the string.

Execution Table

Step	Operation	Node Visited / Value	Pointer Changes	Tree State (Visual)
1	Serialize root	1	root -> 1	1 / ? ?
2	Serialize left child	2	root.left -> 2	1 / 2 ? / ? ?
3	Serialize left.left (null)	#	none	1 / 2 ? / # ?
4	Serialize left.right (null)	#	none	1 / 2 ? / # #
5	Serialize right child	3	root.right -> 3	1 / 2 3 / # #
6	Serialize right.left (null)	#	none	1 / 2 3 / # # / # ?
7	Serialize right.right (null)	#	none	1 / 2 3 / # # / # #
8	Serialization complete	Serialized string: "1,2,#,#,3,#,#"	none	Tree fully serialized
9	Deserialize root	1	root -> 1	1 / ? ?
10	Deserialize left child	2	root.left -> 2	1 / 2 ? / ? ?
11	Deserialize left.left (null)	#	root.left.left -> null	1 / 2 ? / # ?
12	Deserialize left.right (null)	#	root.left.right -> null	1 / 2 ? / # #
13	Deserialize right child	3	root.right -> 3	1 / 2 3 / # #
14	Deserialize right.left (null)	#	root.right.left -> null	1 / 2 3 / # # / # ?
15	Deserialize right.right (null)	#	root.right.right -> null	1 / 2 3 / # # / # #
16	Deserialization complete	Tree rebuilt	none	1 / 2 3 / # # / # #

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

Variable Tracker

Variable	Start	After Step 1	After Step 5	After Step 8	After Step 9	After Step 13	Final
root	null	1	1	1	1	1	1
current node (serialize)	null	1	3	null	null	null	null
serialized string	""	"1"	"1,2,#,#,3"	"1,2,#,#,3,#,#"	"1,2,#,#,3,#,#"	"1,2,#,#,3,#,#"	"1,2,#,#,3,#,#"
nodes queue (deserialize)	empty	empty	empty	empty	[2,#,#,3,#,#]	[#,#]	[]
current node (deserialize)	null	null	null	null	1	3	null

Key Moments - 3 Insights

Why do we use '#' in the serialized string?

The '#' represents a null node (no child). This is crucial to know where the tree branches end during deserialization, as shown in steps 3, 4, 6, 7, 11, 12, 14, and 15 in the execution_table.

Why is preorder traversal used for serialization?

Preorder visits the root before children, allowing us to record the node value first, then its left and right subtrees. This order matches the deserialization process, which reads values in the same sequence (see steps 1-7 for serialization and 9-15 for deserialization).

How does deserialization know when to stop creating nodes?

When the next value is '#', deserialization returns null, indicating no child node. This stops further recursion on that branch, as seen in steps 11, 12, 14, and 15.

Visual Quiz - 3 Questions

Look at the execution_table at step 5. What is the serialized string so far?

A "1,2,#,#"

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

C "1,2"

D "1"

💡 Hint

Check the 'serialized string' variable in variable_tracker after step 5.

At which step does deserialization create the right child of the root node?

A Step 15

B Step 10

C Step 13

D Step 9

💡 Hint

Look at the 'Operation' and 'Pointer Changes' columns in execution_table around steps 9-15.

If we remove '#' symbols from the serialized string, what will happen during deserialization?

A Deserialization will fail to reconstruct the tree correctly.

B Deserialization will work faster.

C The tree will be reconstructed with extra nodes.

D Nothing changes; tree is the same.

💡 Hint

Refer to key_moments about the role of '#' in marking null nodes.

Concept Snapshot

Serialize and Deserialize Binary Tree:
- Serialize: preorder traversal, record node values and '#' for nulls
- Deserialize: read values in order, create nodes or nulls recursively
- '#' marks no child, essential for structure
- Serialization and deserialization are inverse processes
- Use a queue for deserialization to process values in order

Full Transcript

Serialization of a binary tree uses preorder traversal to record each node's value and '#' for null children. This creates a string representing the tree structure. Deserialization reads this string in order, recreating nodes or nulls recursively to rebuild the original tree. The '#' symbol is critical to mark where branches end. The process uses recursion for both serialization and deserialization, ensuring the tree structure is preserved exactly.

Practice

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

easy

A. Delete all nodes in a binary tree

B. Sort the nodes of a binary tree in ascending order

C. Find the height of a binary tree

D. Convert a binary tree to a string and back to a 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 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 it deletes nodes
• Mixing with tree height calculation

2. Which of the following is the correct Java method signature for a serialize function that converts a binary tree to a string?

easy

A. public int serialize(TreeNode root)

B. public void serialize(TreeNode root)

C. public String serialize(TreeNode root)

D. public TreeNode serialize(String data)

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, so parameter is 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, takes root node as input [OK]

Common Mistakes:

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

3. Given the following code snippet for serialization using preorder traversal with '#' as null marker and ',' as separator, what is the output string for the tree below? Tree:

    1
   / \
  2   3
     / \
    4   5

Code snippet:

void serializeHelper(TreeNode root, StringBuilder sb) {
  if (root == null) {
    sb.append("#,");
    return;
  }
  sb.append(root.val).append(",");
  serializeHelper(root.left, sb);
  serializeHelper(root.right, sb);
}

medium

A. 1,2,#,#,3,4,#,#,5,#

B. 1,2,#,#,3,4,#,#,5,#,#,

C. 1,3,2,#,#,4,#,#,5,#,#,

D. 1,2,3,4,5,#,#,#,#,#,#,

Solution

1. Step 1: Perform preorder traversal with null markers

   Visit root: 1, then left subtree: 2, left null (#), right null (#), then right subtree: 3, left: 4, left null (#), right null (#), right: 5, left null (#), right null (#).

2. Step 2: Build string with commas and '#' for nulls

   Concatenate values and null markers with commas: "1,2,#,#,3,4,#,#,5,#,#,"

3. Final Answer:

   1,2,#,#,3,4,#,#,5,#,#, -> Option B

4. Quick Check:

   Preorder + nulls = 1,2,#,#,3,4,#,#,5,#,#, [OK]

Hint: Preorder serialize: root,left,right with '#' for null [OK]

Common Mistakes:

• Missing null markers (#)
• Wrong traversal order
• Omitting trailing commas

4. Identify the bug in the following deserialize method that reconstructs a binary tree from a serialized string using preorder traversal with '#' as null marker:

int index = 0;
TreeNode deserialize(String data) {
  String[] nodes = data.split(",");
  if (nodes[index].equals("#")) {
    index++;
    return null;
  }
  TreeNode root = new TreeNode(Integer.parseInt(nodes[index++]));
  root.left = deserialize(data);
  root.right = deserialize(data);
  return root;
}

medium

A. The index variable should be static or global to maintain state across recursive calls

B. The split method should use ";" instead of ","

C. The method should return a String instead of TreeNode

D. The base case should check for empty string instead of "#"

Solution

1. Step 1: Understand index usage in recursion

   The index variable tracks position in nodes array. It must keep its value across recursive calls to move forward correctly.

2. Step 2: Identify scope problem

   Here, index is a local variable inside the method, so it resets to 0 on each call, causing infinite recursion or wrong tree.

3. Final Answer:

   The index variable should be static or global to maintain state across recursive calls -> Option A

4. Quick Check:

   Index must persist across calls [OK]

Hint: Index must be shared across recursion, use class/global variable [OK]

Common Mistakes:

• Making index local causing reset each call
• Wrong delimiter in split
• Incorrect return type

5. You want to serialize a binary tree and then deserialize it back. However, your tree contains integer values that can be negative, zero, or positive. Which approach below correctly handles all integer values including negatives during serialization and deserialization?

hard

A. Use preorder traversal with ',' as separator and '#' for nulls; parse integers with Integer.parseInt during deserialization

B. Use inorder traversal without null markers; split by spaces; parse integers with Integer.parseInt

C. Use level order traversal but skip null nodes; separate values by commas; parse integers with Integer.parseInt

D. Serialize only positive values and ignore negatives; use preorder traversal

Solution

1. Step 1: Choose traversal and null markers

   Preorder traversal with '#' for nulls ensures structure is preserved, including negative and zero values.

2. Step 2: Parse integers correctly

   Integer.parseInt handles negative, zero, and positive integers correctly during deserialization.

3. Final Answer:

   Use preorder traversal with ',' as separator and '#' for nulls; parse integers with Integer.parseInt during deserialization -> Option A

4. Quick Check:

   Preorder + '#' + Integer.parseInt handles all integers [OK]

Hint: Use preorder + '#' + Integer.parseInt for all integer values [OK]

Common Mistakes:

• Skipping null markers causing wrong tree
• Ignoring negative values
• Using traversal without nulls losing structure