108. Convert Sorted Array to Binary Search Tree

Problem Description

Given a sorted integer array nums, convert it to a height-balanced binary search tree (BST). A height-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.

Solution: Divide and Conquer

The optimal approach is to use a divide-and-conquer strategy. We recursively build the BST by selecting the middle element of the sorted array as the root node. The left half of the array will form the left subtree, and the right half will form the right subtree. This ensures that the resulting tree is balanced.

Algorithm

1. Base Case: If the left index l is greater than the right index r, return null (empty subtree).

2. Find Middle: Calculate the middle index mid = (l + r) / 2.

3. Create Root Node: Create a new tree node with the value at nums[mid] as its value.

4. Recursive Calls: Recursively call the function to build the left subtree (dfs(l, mid - 1)) and the right subtree (dfs(mid + 1, r)).

5. Connect Subtrees: Assign the left and right subtrees to the root node.

6. Return Root: Return the root node.

Time and Space Complexity

• Time Complexity: O(N), where N is the length of the input array. Each element is visited and processed exactly once.
• Space Complexity: O(log N) in the average case and O(N) in the worst case (completely skewed tree). The space complexity comes from the recursive call stack. A balanced tree will have a logarithmic depth, while a skewed tree will have linear depth.

Code Implementation (Python)

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
class Solution:
    def sortedArrayToBST(self, nums: list[int]) -> TreeNode:
        def dfs(l, r):
            if l > r:
                return None
            mid = (l + r) // 2
            root = TreeNode(nums[mid])
            root.left = dfs(l, mid - 1)
            root.right = dfs(mid + 1, r)
            return root
        return dfs(0, len(nums) - 1)
 

Code Implementation (Java)

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
 
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums, 0, nums.length - 1);
    }
 
    private TreeNode dfs(int[] nums, int l, int r) {
        if (l > r) {
            return null;
        }
        int mid = (l + r) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = dfs(nums, l, mid - 1);
        root.right = dfs(nums, mid + 1, r);
        return root;
    }
}

Similar implementations can be written in other languages like C++, JavaScript, and others following the same recursive divide-and-conquer strategy. The core logic remains consistent across all languages.