Compute the Height of a Binary Tree Using Go

This program determines the height of a binary tree. The height of a binary tree is defined as the number of edges in the longest path from the root to a leaf.

Program Explanation

The program uses a recursive function that traverses the tree to calculate the maximum depth from the root to the farthest leaf. This recursive approach simplifies the process of navigating through the tree and finding its height.

Code Structure

1. TreeNode struct: Defines the structure of the binary tree nodes.
2. maxDepth function: Recursively calculates the height of the binary tree from the root node.

Code with Documentation

package main

import (
    "fmt"
    "math"
)

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

// maxDepth calculates the maximum depth or height of the binary tree.
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return 1 + int(math.Max(float64(maxDepth(root.Left)), float64(maxDepth(root.Right))))
}

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

    height := maxDepth(root)
    fmt.Println("Height of the tree is:", height) // Should output 3
}

Conclusion

The Go code effectively calculates the height of a binary tree using a straightforward recursive method, facilitating an intuitive approach to tree traversal. This program is essential for understanding fundamental properties of trees in data structures, which are critical in various applications such as network routing algorithms and organizational hierarchies.