Implement In-order, Pre-order, and Post-order Traversals on a Binary Tree Using Go

This program demonstrates how to perform in-order, pre-order, and post-order traversals of a binary tree using the Go programming language. Each traversal method serves different purposes and is used in various applications like syntax tree evaluations, sorting, and more.

Program Explanation

The code structure includes a TreeNode struct to define the binary tree’s nodes and three functions to implement each of the traversal methods:

Code Structure

1. TreeNode struct: Defines the structure of the binary tree nodes with integer values and pointers to left and right child nodes.
2. inOrder function: Implements in-order traversal (left, root, right).
3. preOrder function: Implements pre-order traversal (root, left, right).
4. postOrder function: Implements post-order traversal (left, right, root).

Code with Documentation

package main

import "fmt"

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

// inOrder performs an in-order traversal of the binary tree.
func inOrder(root *TreeNode) []int {
    var result []int
    if root != nil {
        result = append(result, inOrder(root.Left)...)
        result = append(result, root.Val)
        result = append(result, inOrder(root.Right)...)
    }
    return result
}

// preOrder performs a pre-order traversal of the binary tree.
func preOrder(root *TreeNode) []int {
    var result []int
    if root != nil {
        result = append(result, root.Val)
        result = append(result, preOrder(root.Left)...)
        result = append(result, preOrder(root.Right)...)
    }
    return result
}

// postOrder performs a post-order traversal of the binary tree.
func postOrder(root *TreeNode) []int {
    var result []int
    if root != nil {
        result = append(result, postOrder(root.Left)...)
        result = append(result, postOrder(root.Right)...)
        result = append(result, root.Val)
    }
    return result
}

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

    fmt.Println("In-order traversal:", inOrder(root))
    fmt.Println("Pre-order traversal:", preOrder(root))
    fmt.Println("Post-order traversal:", postOrder(root))
}

Conclusion

The provided Go code effectively demonstrates the three fundamental tree traversal techniques, crucial for various applications including binary search trees, expression parsing, and more. These methods offer insights into the tree’s structure and node relationships.