Serialize and Deserialize Binary Tree in DSA Go - Build from Scratch

Serialize and Deserialize Binary Tree

📖 Scenario: Imagine you are building a system that needs to save and load family trees. Each family tree is a binary tree where each node has a name. You want to convert the tree into a string to save it, and later rebuild the tree from that string.

🎯 Goal: Build a program in Go that can convert a binary tree of names into a string (serialize) and then rebuild the exact same tree from that string (deserialize).

📋 What You'll Learn

Define a binary tree node struct called TreeNode with a Val string and pointers to Left and Right children

Create a function serialize that converts the tree into a string using preorder traversal and # for null nodes

Create a function deserialize that rebuilds the tree from the serialized string

Demonstrate serialization and deserialization with a sample tree

💡 Why This Matters

🌍 Real World

Saving and loading complex tree data structures like family trees, decision trees, or game states requires serialization and deserialization.

💼 Career

Understanding how to convert data structures to strings and back is essential for software engineers working with databases, networking, and file storage.

1

Define the TreeNode struct and create a sample tree

Define a struct called TreeNode with a string field Val and two pointers Left and Right to TreeNode. Then create a variable root that builds this tree:
Root node with value "Alice", left child "Bob", right child "Carol", and Bob has left child "Dave".

DSA Go

// Define TreeNode struct and create the sample tree
// Your code here

Hint

Use a struct with string and pointer fields. Build the tree from bottom up using &TreeNode{Val: "name"} syntax.

2

Create a helper variable for serialized data

Create a variable called result of type string to hold the serialized tree data inside the main function, initialized as an empty string.

DSA Go

package main

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

func main() {
    root := &TreeNode{
        Val: "Alice",
        Left: &TreeNode{
            Val: "Bob",
            Left: &TreeNode{Val: "Dave"},
        },
        Right: &TreeNode{Val: "Carol"},
    }

    // Create a string variable called result to hold serialized data
    // Your code here
}

Hint

Just create a variable result and set it to empty string "".

3

Write the serialize function using preorder traversal

Write a function called serialize that takes a pointer to TreeNode called root and returns a string. Use preorder traversal (root, left, right). For null nodes, add #. Separate values with commas. Use recursion. In main, assign result = serialize(root).

DSA Go

package main

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

func serialize(root *TreeNode) string {
    // Write recursive preorder traversal
    // Your code here
}

func main() {
    root := &TreeNode{
        Val: "Alice",
        Left: &TreeNode{
            Val: "Bob",
            Left: &TreeNode{Val: "Dave"},
        },
        Right: &TreeNode{Val: "Carol"},
    }

    result := ""

    // Call serialize and assign to result
    // Your code here
}

Hint

Use recursion. If node is nil, return "#". Otherwise return value plus serialized left and right with commas.

4

Write the deserialize function and print the tree preorder

Write a function called deserialize that takes a string called data and returns a pointer to TreeNode. Split data by commas into a slice. Use a helper function with an index pointer to rebuild the tree recursively. In main, call deserialize(result) to get newRoot. Then write a function printPreorder that prints node values preorder separated by spaces. Call printPreorder(newRoot) to print the tree.

DSA Go

package main

import (
    "fmt"
    "strings"
)

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

func serialize(root *TreeNode) string {
    if root == nil {
        return "#"
    }
    leftSerialized := serialize(root.Left)
    rightSerialized := serialize(root.Right)
    return root.Val + "," + leftSerialized + "," + rightSerialized
}

func deserialize(data string) *TreeNode {
    // Split data by commas
    // Use helper function with index pointer to rebuild tree
    // Your code here
}

func main() {
    root := &TreeNode{
        Val: "Alice",
        Left: &TreeNode{
            Val: "Bob",
            Left: &TreeNode{Val: "Dave"},
        },
        Right: &TreeNode{Val: "Carol"},
    }

    result := serialize(root)

    // Call deserialize with result and assign to newRoot
    // Write printPreorder function and call it with newRoot
    // Your code here
}

Hint

Split the string by commas. Use a recursive helper with an index pointer to rebuild nodes. For printing, visit root, then left, then right, printing values with spaces.

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