Serialize and Deserialize Binary Tree in DSA Go - Execution Trace

Concept Flow - Serialize and Deserialize Binary Tree

Start at root node

↓

Serialize: Preorder traversal

↓

Record node value or null

↓

Go left subtree

↓

Go right subtree

↓

End serialization

↓

Start deserialization

↓

Read next value

↓

If value is null, return nil

↓

Create node with value

↓

Deserialize left subtree

↓

Deserialize right subtree

↓

Return node

The tree is serialized by visiting nodes in preorder and recording values or nulls. Deserialization reads values in order to rebuild the tree recursively.

Execution Sample

DSA Go

func serialize(root *Node) string {
  if root == nil { return "null," }
  return fmt.Sprintf("%d,", root.Val) + serialize(root.Left) + serialize(root.Right)
}

var index int

func deserialize(data []string) *Node {
  if index >= len(data) {
    return nil
  }
  val := data[index]
  index++
  if val == "null" { return nil }
  node := &Node{Val: atoi(val)}
  node.Left = deserialize(data)
  node.Right = deserialize(data)
  return node
}

This code serializes a binary tree into a string using preorder traversal and deserializes it back recursively.

Execution Table

Step	Operation	Node Visited / Value	Pointer Changes	Tree State (Serialized or Deserialized)
1	Serialize root	Node 1	None	Serialized: "1,"
2	Serialize left child	Node 2	None	Serialized: "1,2,"
3	Serialize left.left	nil	None	Serialized: "1,2,null,"
4	Serialize left.right	nil	None	Serialized: "1,2,null,null,"
5	Serialize right child	Node 3	None	Serialized: "1,2,null,null,3,"
6	Serialize right.left	Node 4	None	Serialized: "1,2,null,null,3,4,"
7	Serialize right.left.left	nil	None	Serialized: "1,2,null,null,3,4,null,"
8	Serialize right.left.right	nil	None	Serialized: "1,2,null,null,3,4,null,null,"
9	Serialize right.right	Node 5	None	Serialized: "1,2,null,null,3,4,null,null,5,"
10	Serialize right.right.left	nil	None	Serialized: "1,2,null,null,3,4,null,null,5,null,"
11	Serialize right.right.right	nil	None	Serialized: "1,2,null,null,3,4,null,null,5,null,null,"
12	Deserialize root	Value 1	Create node 1	Deserialized: Node 1
13	Deserialize left child	Value 2	Create node 2	Deserialized: Node 1 with left 2
14	Deserialize left.left	Value null	Return nil	Deserialized: Node 2 with left nil
15	Deserialize left.right	Value null	Return nil	Deserialized: Node 2 with right nil
16	Deserialize right child	Value 3	Create node 3	Deserialized: Node 1 with right 3
17	Deserialize right.left	Value 4	Create node 4	Deserialized: Node 3 with left 4
18	Deserialize right.left.left	Value null	Return nil	Deserialized: Node 4 with left nil
19	Deserialize right.left.right	Value null	Return nil	Deserialized: Node 4 with right nil
20	Deserialize right.right	Value 5	Create node 5	Deserialized: Node 3 with right 5
21	Deserialize right.right.left	Value null	Return nil	Deserialized: Node 5 with left nil
22	Deserialize right.right.right	Value null	Return nil	Deserialized: Node 5 with right nil
23	End	All values processed	None	Tree fully deserialized

💡 Serialization ends after all nodes visited; deserialization ends after all values processed.

Variable Tracker

Variable	Start	After Step 1	After Step 6	After Step 11	After Step 12	After Step 22	Final
Serialized String	""	"1,"	"1,2,null,null,3,4,null,null,5,null,null,"	"1,2,null,null,3,4,null,null,5,null,null,"	"1,2,null,null,3,4,null,null,5,null,null,"	"1,2,null,null,3,4,null,null,5,null,null,"	"1,2,null,null,3,4,null,null,5,null,null,"
Deserialization Index	0	0	0	0	1	22	22
Current Node	nil	Node 1	Node 3	Node 5	Node 1	Node 5	nil
Tree Size	0	1	4	6	1	6	6

Key Moments - 3 Insights

Why do we record 'null' for missing children during serialization?

Recording 'null' ensures the tree structure is preserved exactly, including where nodes are missing. Without 'null', deserialization cannot know if a child is missing or if the next value belongs to a different subtree (see execution_table steps 3,4).

How does deserialization know when to stop reading left or right subtree?

Deserialization reads values in order. When it reads 'null', it returns nil and moves on. This signals the end of that subtree branch (see execution_table steps 14,15).

Why is preorder traversal used for serialization?

Preorder visits root first, then left, then right. This order allows deserialization to reconstruct the tree top-down easily by reading values in the same order (see concept_flow and execution_table steps 1-11).

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the serialized string so far?

A "1,2,null,null,3,"

B "1,2,null,null,"

C "1,2,null,null,3,4,"

D "1,2,null,null,3,4,null,"

💡 Hint

Check the 'Tree State (Serialized or Deserialized)' column at step 5 in execution_table.

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

A Step 16

B Step 17

C Step 18

D Step 20

💡 Hint

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

If we remove recording 'null' values during serialization, what will happen during deserialization?

A Deserialization will fail to reconstruct the exact tree structure.

B Deserialization will work faster and correctly.

C The serialized string will be longer.

D The tree will be serialized in postorder instead.

💡 Hint

Refer to key_moments about why 'null' is recorded during serialization.

Concept Snapshot

Serialize and Deserialize Binary Tree:
- Serialize using preorder traversal: root, left, right
- Record 'null' for missing children to preserve structure
- Deserialize by reading values in order, creating nodes or nil
- Recursive approach for both serialization and deserialization
- Ensures exact tree structure is saved and restored

Full Transcript

This visualization shows how a binary tree is converted into a string and back. Serialization visits nodes in preorder, recording values or 'null' for missing children. This keeps the tree shape exact. Deserialization reads the string values in order, recreating nodes or nil recursively. The execution table tracks each step, showing how the serialized string grows and how nodes are created during deserialization. Key moments explain why 'null' is needed and why preorder is used. The variable tracker shows how the serialized string and current node change over time. The quiz tests understanding of these steps.