This program demonstrates how to convert a sorted array into a height-balanced Binary Search Tree (BST) using the Go programming language. A balanced BST is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Program Explanation

The process involves selecting the middle element of the array as the root of the BST to ensure balance. The array is then divided into two halves around the middle element. This division and selection process is recursively applied to each half to construct the entire tree.

Code Structure

1. TreeNode struct: Defines the structure of the BST nodes.
2. sortedArrayToBST function: Main function that initiates the recursive process to convert the array into a BST.
3. convert function: Recursive helper function that performs the actual conversion.

Code with Documentation

package main

import (
    "fmt"
)

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

// sortedArrayToBST converts a sorted array into a height-balanced BST.
func sortedArrayToBST(nums []int) *TreeNode {
    if len(nums) == 0 {
        return nil
    }
    return convert(nums, 0, len(nums)-1)
}

// convert is a recursive helper function to convert array slice into a BST.
// It takes a slice of the array along with the start and end indices.
func convert(nums []int, left int, right int) *TreeNode {
    if left > right {
        return nil
    }
    // Mid element to balance the tree
    mid := left + (right - left)/2
    node := &TreeNode{Val: nums[mid]}
    node.Left = convert(nums, left, mid-1)
    node.Right = convert(nums, mid+1, right)
    return node
}

func main() {
    // Example sorted array
    nums := []int{-10, -3, 0, 5, 9}
    bstRoot := sortedArrayToBST(nums)
    fmt.Println("Root of the Balanced BST is:", bstRoot.Val) // Output should show the middle element as root
}

Conclusion

The provided Go code efficiently creates a balanced BST from a sorted array by recursively selecting the middle element as the root. This approach ensures that the resultant BST is height-balanced, optimizing various binary tree operations such as search, insert, and delete.