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.