Convert Sorted Array to Binary Search Tree - Python Solution

1. Introduction

"Convert Sorted Array to Binary Search Tree" is a problem that combines concepts from array manipulation and binary tree construction. The goal is to create a height-balanced binary search tree (BST) from a sorted array. This problem is an excellent exercise in understanding how to construct balanced binary trees and utilize binary search principles.

Problem

Given an integer array nums where the elements are sorted in ascending order, the task is to convert it into a height-balanced binary search tree. A height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than one.

2. Solution Steps

1. Understand the properties of a BST and what makes a tree height-balanced.

2. Use the middle element of the array as the root of the BST to ensure balance.

3. Recursively apply the same logic to the left and right halves of the array to construct the left and right subtrees, respectively.

4. Continue the process until the entire array is converted into a BST.

3. Code Program

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def sortedArrayToBST(nums):
    if not nums:
        return None

    mid = len(nums) // 2
    # The middle element becomes the root
    node = TreeNode(nums[mid])
    # Recursively build the left and right subtrees
    node.left = sortedArrayToBST(nums[:mid])
    node.right = sortedArrayToBST(nums[mid + 1:])

    return node

# Example Usage
root = sortedArrayToBST([-10, -3, 0, 5, 9])

Output:

A height-balanced binary search tree constructed from the given sorted array.

Explanation:

1. Root Selection: The middle element of the array is chosen as the root of the BST to ensure the tree is height-balanced.

2. Recursive Subtree Construction: The array is split into two halves around the middle element. The left half is used to recursively construct the left subtree, and the right half for the right subtree.

3. Height-Balance: By selecting the middle element as the root at each step, the tree remains height-balanced.

4. BST Property: The inorder traversal of the constructed tree will yield the original sorted array, confirming its BST property.