This program checks if a binary tree is height-balanced. A binary tree is considered height-balanced if for every node, the height difference between its left and right subtree is no more than one.

Program Explanation

The approach involves a recursive function that traverses the tree while checking the height of each subtree. The function returns the height of the subtree if it is balanced, and -1 if it finds any part of the tree that is not balanced.

Code Structure

1. TreeNode struct: Defines the structure of the binary tree nodes.
2. isBalanced function: Determines if the binary tree is balanced by invoking a helper function.
3. checkHeight function: Recursive helper function that checks the height of each subtree and determines if the tree is balanced at each node.

Code with Documentation

package main

import (
    "fmt"
    "math"
)

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

// isBalanced checks if the binary tree is height-balanced.
func isBalanced(root *TreeNode) bool {
    return checkHeight(root) != -1
}

// checkHeight returns the height of the subtree if it is balanced, otherwise -1.
func checkHeight(node *TreeNode) int {
    if node == nil {
        return 0
    }

    leftHeight := checkHeight(node.Left)
    if leftHeight == -1 {
        return -1
    }

    rightHeight := checkHeight(node.Right)
    if rightHeight == -1 {
        return -1
    }

    if math.Abs(float64(leftHeight-rightHeight)) > 1 {
        return -1
    }

    return 1 + math.Max(float64(leftHeight), float64(rightHeight))
}

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

    if isBalanced(root) {
        fmt.Println("The tree is balanced.")
    } else {
        fmt.Println("The tree is not balanced.")
    }
}

Conclusion

The Go code efficiently checks if a binary tree is height-balanced using a depth-first traversal approach. This ensures that the function can early terminate if any part of the tree is unbalanced, thereby optimizing performance. This functionality is crucial for applications that require well-formed binary trees for quick operations, such as AVL trees used in databases.