This program demonstrates how to serialize a binary tree into a string format and then deserialize it back into the original tree structure using the Go programming language. Serialization of a binary tree is crucial for scenarios like saving the tree to a file or transmitting it over a network.

Program Explanation

The serialization process involves converting the binary tree into a string representation using pre-order traversal, where null nodes are denoted by some marker (e.g., ‘#’). Deserialization takes this string and reconstructs the original binary tree structure.

Code Structure

1. TreeNode struct: Defines the structure of the binary tree nodes.
2. Serialize function: Serializes the binary tree into a string.
3. Deserialize function: Reconstructs the binary tree from the serialized string.

Code with Documentation

package main

import (
    "fmt"
    "strings"
    "strconv"
)

// TreeNode defines a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// Serialize serializes the binary tree into a string.
func Serialize(root *TreeNode) string {
    var result strings.Builder
    serializeHelper(root, &result)
    return result.String()
}

// serializeHelper is a recursive helper function for Serialize.
func serializeHelper(node *TreeNode, result *strings.Builder) {
    if node == nil {
        result.WriteString("# ")
        return
    }
    result.WriteString(strconv.Itoa(node.Val) + " ")
    serializeHelper(node.Left, result)
    serializeHelper(node.Right, result)
}

// Deserialize deserializes the string back to a binary tree.
func Deserialize(data string) *TreeNode {
    values := strings.Fields(data)
    var index int
    return deserializeHelper(values, &index)
}

// deserializeHelper is a recursive helper function for Deserialize.
func deserializeHelper(values []string, index *int) *TreeNode {
    if values[*index] == "#" {
        *index++
        return nil
    }
    val, _ := strconv.Atoi(values[*index])
    *index++
    node := &TreeNode{Val: val}
    node.Left = deserializeHelper(values, index)
    node.Right = deserializeHelper(values, index)
    return node
}

func main() {
    // Example tree construction
    root := &TreeNode{Val: 1, Left: &TreeNode{Val: 2}, Right: &TreeNode{Val: 3, Left: &TreeNode{Val: 4}, Right: &TreeNode{Val: 5}}}
    serialized := Serialize(root)
    fmt.Println("Serialized tree:", serialized)
    deserialized := Deserialize(serialized)
    fmt.Println("Deserialized tree root value:", deserialized.Val) // Should output 1
}

Conclusion

The provided Go code efficiently manages the serialization and deserialization of a binary tree, allowing the tree structure to be stored as a string and then reconstructed as needed. This functionality is critical for applications involving persistent storage or network transmission of binary trees.