Python Program to Convert a Sorted Array to a Balanced BST

This program demonstrates how to convert a sorted array into a balanced Binary Search Tree (BST). A balanced BST is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than one. The process to convert involves recursively dividing the array and creating a tree node for each division.

class TreeNode:
    """Definition of a TreeNode for a Binary Search Tree (BST)."""
    def __init__(self, x):
        """
        Initialize the tree node.
        
        :param x: int, the integer value of the node
        """
        self.val = x
        self.left = None
        self.right = None

class Solution:
    """Solution class to handle conversion from array to BST."""
    def sortedArrayToBST(self, nums):
        """
        Convert a sorted array to a height balanced BST.
        
        :param nums: List[int], sorted array of integers
        :return: TreeNode, the root of the balanced BST
        """
        if not nums:
            return None
        
        def convert(left, right):
            """
            Recursive helper function to convert array to BST.
            
            :param left: int, left index of the subarray
            :param right: int, right index of the subarray
            :return: TreeNode, the root node of the current subtree
            """
            if left > right:
                return None
            
            # Middle element to maintain balance
            mid = (left + right) // 2
            node = TreeNode(nums[mid])
            
            # Recursively construct the left subtree
            node.left = convert(left, mid - 1)
            # Recursively construct the right subtree
            node.right = convert(mid + 1, right)
            return node
        
        return convert(0, len(nums) - 1)

# Example Usage
if __name__ == "__main__":
    # Sorted array
    nums = [-10, -3, 0, 5, 9]
    
    # Instance of Solution
    sol = Solution()
    
    # Convert and get the root of the balanced BST
    bst_root = sol.sortedArrayToBST(nums)
    print(f"Root of the balanced BST is: {bst_root.val}")

The Solution class includes the method sortedArrayToBST, which utilizes a helper function convert to perform recursive division of the array. By selecting the middle element as the root for each segment, it ensures the BST remains balanced. The recursive division continues until the entire array is converted into a BST.