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.