Convert Sorted Array to Height-Balanced BST

Converting a sorted array to a height-balanced binary search tree is a classic algorithm problem that demonstrates the relationship between sorted data and BST properties, requiring careful consideration of tree balancing strategies.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. Are we guaranteed that the input array is sorted in ascending order, or could it be descending?
2. Can we modify the input array during processing, or must we work with a copy?
3. Should we return the root node of the BST or the entire tree structure?
4. Do we need to maintain a balanced BST, or is any valid BST construction acceptable?
5. What's the expected time complexity for the solution? Are we aiming for O(n) or can we accept O(n log n)?

Restate the pattern or problem type in your own words: This pattern involves converting between sorted arrays and Binary Search Trees (BSTs). The key insight is that a sorted array can be used to construct a height-balanced BST by recursively selecting the middle element as the root, ensuring that left and right subtrees have approximately equal numbers of nodes.

Clarify the signal words and constraint shape that point to it:

• "Sorted array" or "sorted input"
• "Binary Search Tree" or "BST"
• "Balanced tree" or "height balanced"
• "Convert" or "transform between representations"

Note any assumptions you are making:

• The input array is sorted in ascending order (most common assumption)
• We want to create a height-balanced BST for optimal performance
• The array elements are unique (no duplicates in typical implementations)
• We can use recursion or iterative approaches

Identify whether the pattern is best suited for static, streaming, or online scenarios if relevant: This pattern is primarily suited for static scenarios where the entire input is available upfront. It's not ideal for streaming data because we need to know the complete sorted sequence to build a balanced BST. For online scenarios, we'd likely want a self-balancing tree like AVL or Red-Black trees instead of constructing from a pre-sorted array.

2. When to Use This Pattern

Signal words and constraint shapes in a problem statement that indicate this pattern:

• "Given a sorted array" or "array is sorted in ascending order"
• "Convert to balanced BST" or "construct BST from sorted data"
• "Return array in sorted order" (reverse direction)
• "Must be height-balanced" or "balanced binary search tree"
• "In-order traversal should match input"

Why this pattern fits better than the most common alternatives: This pattern is specifically suited for problems where we have sorted input and need to construct a height-balanced BST, or vice versa. Unlike general tree construction approaches that might result in skewed trees with O(n) depth, this pattern leverages the sorted property to build optimal balanced structures. The key advantage over linear insertion approaches (which would create O(n²) worst-case trees) is that we can build a truly balanced tree in O(n) time by choosing the middle element as root at each step.

Conditions where a variation or related pattern applies instead:

• If input is not sorted, we'd need to sort first (O(n log n)) or use a general BST construction approach
• If we only need to convert between data structures without maintaining BST properties, simpler approaches suffice
• For streaming input where elements arrive one-by-one, we'd use dynamic BST insertion rather than batch construction

The core insight that makes this pattern work: The key insight is that for any sorted array, if we recursively choose the middle element as the root and build left/right subtrees from the remaining portions, we ensure that each subtree contains approximately equal numbers of nodes. This naturally creates a height-balanced tree structure, which is optimal for search operations with O(log n) complexity.

This pattern represents a fundamental application of divide-and-conquer principles in tree construction, where the sorted nature of input allows us to make optimal partitioning decisions at each step.

3. Approach Evolution

Interview communication script:

"My first instinct is to think about how I can convert a sorted array into a BST. The most straightforward approach would be to pick the middle element as the root and recursively build left and right subtrees, but that's not immediately obvious why it works. Let me think about this more carefully.

If I just pick any element as root, I could end up with a highly unbalanced tree. But if I always pick the middle element, I'm ensuring that roughly half the elements go to the left and half to the right. This is key - it maintains balance, which gives us O(log n) height for the tree.

But wait, let me think about what happens if I don't maintain this balance. If I just build a BST by inserting elements one by one in sorted order, I'd get a linked list-like structure with O(n) height. That's not what we want.

So the key insight is that to build a balanced BST from a sorted array, I need to maintain balance at each step. By choosing the middle element as root, I ensure that the left and right subtrees have nearly equal numbers of nodes. This is the crucial invariant.

Let me trace through an example to make sure I understand this correctly. If I have [1,2,3,4,5], the middle element is 3. So 3 becomes root, elements [1,2] go to left subtree, and [4,5] go to right subtree. Then I recursively apply the same logic to those subarrays.

This approach gives us O(n log n) time complexity because we process each element once, and for each element we do O(log n) work to find where to place it in the tree structure. But actually, if we're building from sorted array, we can do better - O(n) time by directly constructing the balanced structure.

Let me think about this more systematically. The approach that works is to recursively divide and assign the middle element as root, which naturally creates a balanced tree. This is O(n) time and O(log n) space for recursion stack."

Brute-force approach and why it is not ideal:

The brute force approach would be to build a BST by inserting elements one by one from the sorted array in order. This creates an unbalanced tree where each insertion requires traversing down to find the correct position, resulting in O(n²) time complexity in worst case and O(n log n) average case. This approach fails to maintain the balance property that makes BSTs efficient for search operations.

Improved approach and the key optimization:

The improved approach is to use divide-and-conquer strategy. Since we have a sorted array, we can recursively select the middle element as root to ensure balance. This works because:

1. Middle element ensures roughly equal elements on both sides
2. Each recursive call processes a subarray of size n/2
3. We build the tree structure directly without intermediate insertion steps

Final approach with step-by-step reasoning:

1. Base case: If left > right, return null (empty subtree)
2. Find root: Select middle element of current subarray as root node
3. Build left subtree: Recursively build from left half (elements before middle)
4. Build right subtree: Recursively build from right half (elements after middle)
5. Return root: Return the constructed subtree

The key invariant maintained is that at each recursive step, we select the median element to ensure balanced tree construction. This guarantees O(log n) height for the resulting BST.

Important invariants that must hold:

1. Balance invariant: At every recursive step, the root is chosen as the median element to maintain balanced structure
2. Sorted property: Elements in left subtree are all less than root, elements in right subtree are all greater than root
3. Range invariant: For any subarray, we process elements in their correct relative order to maintain BST property
4. Index bounds: Left and right pointers properly define the current subarray being processed

4. Data Structure Choice

For converting between sorted arrays and BSTs, the primary data structure is a BinaryTreeNode class that represents each node in the binary search tree. Each node needs to store:

• An integer value (the data)
• References to left and right child nodes

The BST property is maintained where for any node:

• All values in the left subtree are less than the node's value
• All values in the right subtree are greater than the node's value

The array serves as the input/output container and is used to:

• Store sorted values for conversion from array to BST
• Collect values during in-order traversal for conversion from BST to array

Why this choice works:

• The TreeNode structure naturally models the tree's hierarchical nature
• Arrays provide O(1) random access for indexing, which is crucial for the divide-and-conquer approach
• The BST property ensures that in-order traversal produces sorted output

Time and space impact:

• Space complexity is O(n) for storing n nodes in the tree
• The array uses O(n) space but is just a container for input/output data
• No additional helper structures are needed beyond the basic tree node structure

Helper structures:

• For the conversion from array to BST, we don't need additional containers beyond the input array
• For conversion from BST to sorted array, we use an ArrayList to collect results during in-order traversal

The simplicity of using basic TreeNode and array structures makes the solution clean, readable, and efficient without unnecessary abstraction.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step by step.

Example: Input array = [-10, -3, 0, 5, 9]

Step 1: Start with the full range [0, 4]

• Mid index = (0 + 4) / 2 = 2
• Value at mid = 0 → This becomes the root node
• Left subtree range: [0, 1]
• Right subtree range: [3, 4]

Step 2: Process left subtree [0, 1]

• Mid index = (0 + 1) / 2 = 0
• Value at mid = -10 → This becomes left child of root
• Left subtree range: [0, -1] (empty)
• Right subtree range: [1, 1]
• For [1, 1]: Mid index = 1, Value = -3 → This becomes right child of -10

Step 3: Process right subtree [3, 4]

• Mid index = (3 + 4) / 2 = 3
• Value at mid = 5 → This becomes right child of root
• Left subtree range: [3, 2] (empty)
• Right subtree range: [4, 4]
• For [4, 4]: Mid index = 4, Value = 9 → This becomes right child of 5

Final Tree Structure:

        0
       / \
     -10   5
      \   / \
     -3  9   null

Key observations:

1. The algorithm always selects the middle element to maintain balance
2. Each recursive call processes a subarray, ensuring we build from the root down to leaves
3. The invariants maintained are that left subtree contains elements < root and right subtree contains elements > root
4. The algorithm handles edge cases like single elements and empty ranges naturally

Edge case handling:

• Empty range [i, i-1] returns null (base case)
• Single element range [i, i] creates a leaf node
• The recursive structure naturally handles all boundary conditions

This approach ensures the resulting BST is height-balanced, which is crucial for maintaining O(log n) search times.

6. Java Solution

/**
 * Definition for a binary tree node.
 * public 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) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        
        return buildBST(nums, 0, nums.length - 1);
    }
    
    private TreeNode buildBST(int[] nums, int left, int right) {
        // Base case: when left > right, there are no elements to process
        if (left > right) {
            return null;
        }
        
        // Choose middle element to maintain balance
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        
        // Recursively build left and right subtrees
        root.left = buildBST(nums, left, mid - 1);
        root.right = buildBST(nums, mid + 1, right);
        
        return root;
    }
}

This solution converts a sorted array into a height-balanced binary search tree by recursively selecting the middle element as the root, ensuring that the left and right subtrees have approximately equal numbers of nodes. The approach uses a divide-and-conquer strategy with O(n) time complexity and O(log n) space complexity due to the recursion stack.

7. Complexity Analysis

Time Complexity: O(n) where n is the number of nodes in the tree. Each node is visited exactly once during the construction process, and the work done at each node is constant time.

Space Complexity: O(log n) for the recursion stack in the case of a balanced tree, or O(n) in the worst case for a skewed tree. This space is used to maintain the call stack during the recursive construction process.

Why these bounds are correct:

• The algorithm performs a single traversal of the array elements, visiting each element exactly once to construct the BST.
• The recursion depth is at most log n for a balanced tree (height of the tree), and at most n for a skewed tree where each node has only one child.
• The space complexity is dominated by the recursion stack depth, not by any additional data structures used.

Optimality: This solution is optimal for the problem as stated. We must process each element at least once to build the tree, and the construction itself requires O(n) time. The space complexity is optimal for a recursive approach with balanced input - we cannot avoid the O(log n) recursion stack space in the average case. The solution achieves the best possible time complexity of O(n) and near-optimal space complexity for a recursive implementation.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty array: Should return null for the root node
• Single element: Should create a valid leaf node with no children
• Two elements: Must handle proper balancing to avoid null pointer exceptions

Duplicate Values and Repeated States

• The problem assumes unique values in the array, but if duplicates exist, they should be handled consistently
• When duplicates are present, BST insertion rules determine placement (left subtree for equal values)
• If the array has repeated elements, the resulting BST structure may vary based on insertion strategy

Boundary Conditions

• Single element array: arr[0] becomes root with no children
• Two elements: arr[0] as left child, arr[1] as right child (or vice versa depending on implementation)
• Large arrays: Stack overflow risk with recursive approaches due to deep call stacks

Common Implementation Mistakes

• Off-by-one errors in index calculation: Using left + right instead of (left + right) / 2 can cause infinite recursion or wrong midpoints
• Not handling null checks: Failing to check for null inputs or array bounds before accessing elements
• Incorrect boundary handling: Forgetting to include left <= right condition in the base case, leading to array index out of bounds
• Recursive stack overflow: Using deep recursion for large arrays without tail optimization or iterative alternatives

Implementation-specific Pitfalls

• Integer overflow: In very large arrays, (left + right) / 2 can overflow; use left + (right - left) / 2 instead
• Array bounds: Not validating that indices don't exceed array length when building nodes
• Node creation order: Creating nodes in wrong sequence can lead to incorrect tree structure

// Example of integer overflow issue:
// int mid = (left + right) / 2; // Can overflow for large indices
int mid = left + (right - left) / 2; // Safe alternative

9. Alternative Approaches

There are several alternative approaches to solving the sorted array to BST problem, each with different trade-offs:

1. In-order traversal with array reconstruction: Instead of building the BST directly, we can first perform an in-order traversal of the desired BST to get the sorted array, then build the tree from that array. This approach requires two passes through the data and is less efficient.

2. Iterative construction with stack: Rather than using recursion, we can build the BST iteratively using a stack to simulate the recursive calls. This approach avoids potential stack overflow issues with very large arrays but adds complexity to the implementation.

3. Two-pass approach: First, build a balanced BST by inserting elements one by one in sorted order, then rebalance the tree. This approach is more complex and less efficient than the direct construction method.

4. Using a sorted array as a "source of truth": We can maintain the original sorted array and build the BST by selecting elements from it, which is essentially the same as our approach but with a different mental model.

The chosen solution is optimal because it directly constructs the balanced BST in a single pass with O(n) time and O(log n) space complexity. The alternatives either increase time complexity, add unnecessary steps, or complicate the implementation without providing significant benefits. Our approach is superior because it leverages the sorted nature of the input to build a height-balanced tree efficiently, which is the core requirement of this problem.

10. Test Cases

// Test case 1: Basic balanced BST
// Input: [1,2,3,4,5,6,7]
// Expected output: [1,2,3,4,5,6,7] (in-order traversal)
// BST structure:
//       4
//      / \
//     2   6
//    / \ / \
//   1  3 5  7

// Test case 2: Even number of nodes
// Input: [1,2,3,4]
// Expected output: [1,2,3,4] 
// BST structure:
//     2
//    / \
//   1   3
//        \
//         4

// Test case 3: Single node
// Input: [5]
// Expected output: [5]

// Test case 4: Empty array
// Input: []
// Expected output: []

// Test case 5: Duplicate values (if allowed)
// Input: [1,1,2,2,3,3]
// Expected output: [1,1,2,2,3,3] (in-order traversal)

public 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;
    }
}

public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) return null;
        return buildBST(nums, 0, nums.length - 1);
    }
    
    private TreeNode buildBST(int[] nums, int left, int right) {
        if (left > right) return null;
        
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        
        root.left = buildBST(nums, left, mid - 1);
        root.right = buildBST(nums, mid + 1, right);
        
        return root;
    }
    
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorder(root, result);
        return result;
    }
    
    private void inorder(TreeNode root, List<Integer> result) {
        if (root == null) return;
        inorder(root.left, result);
        result.add(root.val);
        inorder(root.right, result);
    }
}

11. Final Summary

The core idea is to leverage the sorted property of the input array to construct a height-balanced BST by recursively selecting the middle element as the root, ensuring optimal partitioning at each level. This approach works because choosing the median guarantees that left and right subtrees will have approximately equal heights, minimizing the overall tree depth. The solution is optimal with O(n) time complexity and O(log n) space complexity due to the recursive call stack, making it both time-efficient and memory-conscious for balanced BST construction from sorted arrays.