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.

Practice

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

easy

A. Convert a binary tree into a string and back to a tree

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

C. Calculate the height of a binary tree

D. Delete all nodes in 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.

2. Step 2: Understand deserialization

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

3. Final Answer:

   Convert a binary tree into a string and back to a tree -> Option A

4. Quick Check:

   Serialize/Deserialize = Convert tree to string and back [OK]

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

Common Mistakes:

• Confusing serialization with sorting
• Thinking serialization deletes nodes
• Mixing serialization with tree height calculation

2. Which of the following Go function signatures correctly represents a deserialize function for a binary tree?

easy

A. func deserialize(root *TreeNode) string

B. func deserialize(data int) *TreeNode

C. func deserialize(data string) *TreeNode

D. func deserialize(data []int) int

Solution

1. Step 1: Identify input and output types

   Deserialize takes a string (serialized data) and returns a pointer to the root node of the tree.

2. Step 2: Match function signature

   func deserialize(data string) *TreeNode matches this: input is string, output is *TreeNode pointer.

3. Final Answer:

   func deserialize(data string) *TreeNode -> Option C

4. Quick Check:

   Deserialize input string, output tree node pointer [OK]

Hint: Deserialize input is string, output is tree root pointer [OK]

Common Mistakes:

• Using int instead of string as input
• Returning string instead of tree node
• Confusing serialize and deserialize signatures

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 output of the deserialized tree?

medium

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

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

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

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

Solution

1. Step 1: Reconstruct tree from preorder string

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

2. Step 2: Draw tree and find inorder traversal

   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 D

4. Quick Check:

   Inorder traversal = [2,1,4,3,5] [OK]

Hint: Draw tree from preorder, then do left-root-right for inorder [OK]

Common Mistakes:

• Mixing preorder and inorder traversal orders
• Ignoring null markers '#' in deserialization
• Incorrectly placing children nodes

4. Consider this Go code snippet for deserializing a binary tree. What is the bug?

func deserialize(data string) *TreeNode {
    vals := strings.Split(data, ",")
    var index int
    var build func() *TreeNode
    build = func() *TreeNode {
        if vals[index] == "#" {
            index++
            return nil
        }
        node := &TreeNode{Val: vals[index]}
        index++
        node.Left = build()
        node.Right = build()
        return node
    }
    return build()
}

medium

A. TreeNode.Val should be converted from string to int

B. Index variable should be global, not local

C. Strings.Split should use space instead of comma

D. The build function should not be recursive

Solution

1. Step 1: Check TreeNode.Val assignment

   vals[index] is a string, but TreeNode.Val expects an int. Conversion is missing.

2. Step 2: Identify fix

   Use strconv.Atoi(vals[index]) to convert string to int before assigning.

3. Final Answer:

   TreeNode.Val should be converted from string to int -> Option A

4. Quick Check:

   String to int conversion missing [OK]

Hint: Convert string to int before assigning to node value [OK]

Common Mistakes:

• Forgetting to convert string to int
• Changing index scope unnecessarily
• Misusing Split delimiter

5. You want to serialize a binary tree so that it can be stored and later deserialized exactly as it was. Which approach best handles trees with duplicate values and null nodes?

hard

A. Use inorder traversal without null markers

B. Use preorder traversal with a special marker for null nodes

C. Use postorder traversal ignoring null nodes

D. Store only node values in a list without structure

Solution

1. Step 1: Understand serialization needs

   To reconstruct the exact tree, we must record node order and null positions.

2. Step 2: Evaluate options

   Preorder with null markers records structure and values including duplicates. Inorder or postorder without nulls loses structure. Storing only values loses tree shape.

3. Final Answer:

   Use preorder traversal with a special marker for null nodes -> Option B

4. Quick Check:

   Preorder + null markers preserves structure and duplicates [OK]

Hint: Preorder + null markers saves full tree structure [OK]

Common Mistakes:

• Ignoring null nodes in serialization
• Using inorder without nulls loses tree shape
• Assuming values alone define tree