Serialize and Deserialize Binary Tree in DSA Go

Mental Model

We turn a tree into a string to save or send it, then rebuild the exact tree from that string.

Analogy: Like writing a family tree on paper and later using that paper to redraw the same family tree exactly.

    1
   / \
  2   3
     / \
    4   5

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2 and right child 3; 3 has children 4 and 5

Goal: Convert the tree into a string and then rebuild the same tree from that string

Step 1: Start serialization at root node 1

Serialize: "1,"

Why: We record the root value first to know where the tree starts

Step 2: Serialize left child 2

Serialize: "1,2,"

Why: We record left subtree next to keep order

Step 3: Serialize left and right children of 2 which are null

Serialize: "1,2,null,null,"

Why: We mark nulls to know where branches end

Step 4: Serialize right child 3

Serialize: "1,2,null,null,3,"

Why: Continue with right subtree

Step 5: Serialize left child 4 of 3

Serialize: "1,2,null,null,3,4,"

Why: Record left child of 3

Step 6: Serialize left and right children of 4 which are null

Serialize: "1,2,null,null,3,4,null,null,"

Why: Mark nulls for 4's children

Step 7: Serialize right child 5 of 3

Serialize: "1,2,null,null,3,4,null,null,5,"

Why: Record right child of 3

Step 8: Serialize left and right children of 5 which are null

Serialize: "1,2,null,null,3,4,null,null,5,null,null,"

Why: Mark nulls for 5's children

Step 9: Start deserialization from string

Deserialize: reading "1" creates root node 1

Why: We rebuild root first

Step 10: Deserialize left subtree starting with "2"

Deserialize: node 2 as left child of 1

Why: Left subtree comes next

Step 11: Deserialize nulls for 2's children

Deserialize: left and right children of 2 are null

Why: Leaves end here

Step 12: Deserialize right subtree starting with "3"

Deserialize: node 3 as right child of 1

Why: Right subtree next

Step 13: Deserialize left child 4 of 3

Deserialize: node 4 as left child of 3

Why: Left child of 3

Step 14: Deserialize nulls for 4's children

Deserialize: left and right children of 4 are null

Why: Leaves end here

Step 15: Deserialize right child 5 of 3

Deserialize: node 5 as right child of 3

Why: Right child of 3

Step 16: Deserialize nulls for 5's children

Deserialize: left and right children of 5 are null

Why: Leaves end here

Result:

Final tree rebuilt exactly as:
    1
   / \
  2   3
     / \
    4   5

Annotated Code

DSA Go

package main

import (
	"fmt"
	"strings"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// serialize converts tree to string using preorder traversal
func serialize(root *TreeNode) string {
	var sb strings.Builder
	var helper func(node *TreeNode)
	helper = func(node *TreeNode) {
		if node == nil {
			sb.WriteString("null,") // mark null nodes
			return
		}
		sb.WriteString(fmt.Sprintf("%d,", node.Val)) // record node value
		helper(node.Left)  // serialize left subtree
		helper(node.Right) // serialize right subtree
	}
	helper(root)
	return sb.String()
}

// deserialize rebuilds tree from string
func deserialize(data string) *TreeNode {
	vals := strings.Split(data, ",")
	index := 0
	var helper func() *TreeNode
	helper = func() *TreeNode {
		if index >= len(vals) || vals[index] == "null" {
			index++ // skip null
			return nil
		}
		val := vals[index]
		index++
		var num int
		fmt.Sscanf(val, "%d", &num) // parse int
		node := &TreeNode{Val: num}
		node.Left = helper()  // build left subtree
		node.Right = helper() // build right subtree
		return node
	}
	return helper()
}

func printTree(root *TreeNode) {
	if root == nil {
		return
	}
	fmt.Printf("%d -> ", root.Val)
	printTree(root.Left)
	printTree(root.Right)
}

func main() {
	// Build tree: 1
	//           /   \
	//          2     3
	//               / \
	//              4   5
	root := &TreeNode{1, &TreeNode{2, nil, nil}, &TreeNode{3, &TreeNode{4, nil, nil}, &TreeNode{5, nil, nil}}}

	serialized := serialize(root)
	fmt.Println("Serialized:", serialized)

	deserialized := deserialize(serialized)
	fmt.Print("Deserialized preorder: ")
	printTree(deserialized)
	fmt.Println("null")
}

if node == nil { sb.WriteString("null,"); return }

mark null nodes to remember tree shape

sb.WriteString(fmt.Sprintf("%d,", node.Val))

record current node value

helper(node.Left)

serialize left subtree recursively

helper(node.Right)

serialize right subtree recursively

if index >= len(vals) || vals[index] == "null" { index++; return nil }

detect null nodes and skip

fmt.Sscanf(val, "%d", &num)

convert string to integer value

node.Left = helper()

rebuild left subtree recursively

node.Right = helper()

rebuild right subtree recursively

Output

Serialized: 1,2,null,null,3,4,null,null,5,null,null,

Deserialized preorder: 1 -> 2 -> 3 -> 4 -> 5 -> null

Complexity Analysis

Time: O(n) because we visit each node once during serialization and once during deserialization

Space: O(n) because the serialized string and recursion stack both grow with number of nodes

vs Alternative: Compared to storing tree as nested objects, serialization allows easy saving and sending as text with linear cost

Edge Cases

Empty tree (root is nil)

Serialization returns "null," and deserialization returns nil tree

DSA Go

if node == nil { sb.WriteString("null,"); return }

Tree with single node

Serialization records node value and two nulls; deserialization rebuilds single node

DSA Go

if index >= len(vals) || vals[index] == "null" { index++; return nil }

Tree with only left or only right children

Nulls correctly mark missing children so tree shape is preserved

DSA Go

if node == nil { sb.WriteString("null,"); return }

When to Use This Pattern

When you need to save or transfer a tree structure and later rebuild it exactly, use serialize/deserialize pattern to convert between tree and string.

Common Mistakes

Mistake: Not recording null nodes during serialization
Fix: Always write "null," for nil children to keep tree shape

Mistake: Not advancing index after reading null during deserialization
Fix: Increment index when encountering "null" to avoid infinite loop

Summary

It converts a binary tree to a string and back to the same tree.

Use it when you want to save or send a tree and restore it later.

Remember to record null children to keep the exact tree shape.

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