Convert Sorted Array to Binary Search Tree

Convert a sorted array to a height-balanced binary search tree.

Language Selection

Choose your preferred programming language

Showing: Python

Convert Sorted Array to Binary Search Tree

Problem Statement

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than 1.

Examples

Example 1:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:
    0
   / \
 -3   9
 /   /
-10  5

Example 2:

Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.

Constraints

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums is sorted in a strictly increasing order

Approach 1: Recursive Divide and Conquer

Algorithm

Use divide and conquer approach by recursively selecting the middle element as root and building left and right subtrees.

Steps:

Find the middle element of the array
Create root node with middle element
Recursively build left subtree with left half of array
Recursively build right subtree with right half of array
Return the root node

Implementation

Python:

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

def sortedArrayToBST(nums):
    """
    Convert sorted array to height-balanced BST using divide and conquer
    Time: O(n)
    Space: O(log n) for recursion stack
    """
    if not nums:
        return None
    
    # Find middle element
    mid = len(nums) // 2
    
    # Create root with middle element
    root = TreeNode(nums[mid])
    
    # Recursively build left and right subtrees
    root.left = sortedArrayToBST(nums[:mid])
    root.right = sortedArrayToBST(nums[mid + 1:])
    
    return root

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 {
    /**
     * Convert sorted array to height-balanced BST using divide and conquer
     * Time: O(n)
     * Space: O(log n) for recursion stack
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        return buildBST(nums, 0, nums.length - 1);
    }
    
    private TreeNode buildBST(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        
        // Find middle element
        int mid = left + (right - left) / 2;
        
        // Create root with middle element
        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;
    }
}

Go:

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// sortedArrayToBST - Convert sorted array to height-balanced BST using divide and conquer
// Time: O(n)
// Space: O(log n) for recursion stack
func sortedArrayToBST(nums []int) *TreeNode {
    return buildBST(nums, 0, len(nums)-1)
}

func buildBST(nums []int, left, right int) *TreeNode {
    if left > right {
        return nil
    }
    
    // Find middle element
    mid := left + (right-left)/2
    
    // Create root with middle element
    root := &TreeNode{Val: nums[mid]}
    
    // Recursively build left and right subtrees
    root.Left = buildBST(nums, left, mid-1)
    root.Right = buildBST(nums, mid+1, right)
    
    return root
}

JavaScript:

class TreeNode {
    constructor(val, left, right) {
        this.val = (val === undefined ? 0 : val);
        this.left = (left === undefined ? null : left);
        this.right = (right === undefined ? null : right);
    }
}

/**
 * Convert sorted array to height-balanced BST using divide and conquer
 * Time: O(n)
 * Space: O(log n) for recursion stack
 */
function sortedArrayToBST(nums) {
    return buildBST(nums, 0, nums.length - 1);
}

function buildBST(nums, left, right) {
    if (left > right) {
        return null;
    }
    
    // Find middle element
    const mid = left + Math.floor((right - left) / 2);
    
    // Create root with middle element
    const 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;
}

C#:

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    /// <summary>
    /// Convert sorted array to height-balanced BST using divide and conquer
    /// Time: O(n)
    /// Space: O(log n) for recursion stack
    /// </summary>
    public TreeNode SortedArrayToBST(int[] nums) {
        return BuildBST(nums, 0, nums.Length - 1);
    }
    
    private TreeNode BuildBST(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        
        // Find middle element
        int mid = left + (right - left) / 2;
        
        // Create root with middle element
        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;
    }
}

Complexity Analysis

Time Complexity: O(n) where n is the length of the array
Space Complexity: O(log n) for the recursion stack

Approach 2: Iterative with Stack

Algorithm

Use an iterative approach with a stack to simulate the recursive process.

Steps:

Use a stack to store ranges and corresponding parent nodes
Process each range by finding the middle element
Create nodes and push child ranges onto the stack
Continue until all ranges are processed

Implementation

Python:

def sortedArrayToBSTIterative(nums):
    """
    Convert sorted array to BST using iterative approach with stack
    Time: O(n)
    Space: O(log n)
    """
    if not nums:
        return None
    
    # Stack stores (left, right, parent, is_left_child)
    stack = [(0, len(nums) - 1, None, False)]
    root = None
    
    while stack:
        left, right, parent, is_left = stack.pop()
        
        if left > right:
            continue
        
        # Find middle element
        mid = left + (right - left) // 2
        
        # Create current node
        node = TreeNode(nums[mid])
        
        if parent is None:
            root = node
        elif is_left:
            parent.left = node
        else:
            parent.right = node
        
        # Push child ranges onto stack
        stack.append((left, mid - 1, node, True))
        stack.append((mid + 1, right, node, False))
    
    return root

Java:

import java.util.Stack;

public TreeNode sortedArrayToBSTIterative(int[] nums) {
    /**
     * Convert sorted array to BST using iterative approach with stack
     * Time: O(n)
     * Space: O(log n)
     */
    if (nums.length == 0) {
        return null;
    }
    
    Stack<int[]> stack = new Stack<>();
    TreeNode root = new TreeNode(nums[nums.length / 2]);
    stack.push(new int[]{0, nums.length - 1, nums.length / 2});
    
    while (!stack.isEmpty()) {
        int[] range = stack.pop();
        int left = range[0];
        int right = range[1];
        int mid = range[2];
        
        if (left < mid) {
            int leftMid = left + (mid - left) / 2;
            TreeNode leftNode = new TreeNode(nums[leftMid]);
            // Find parent and attach
            attachToParent(root, leftNode, left, mid - 1);
            stack.push(new int[]{left, mid - 1, leftMid});
        }
        
        if (mid < right) {
            int rightMid = mid + 1 + (right - mid - 1) / 2;
            TreeNode rightNode = new TreeNode(nums[rightMid]);
            // Find parent and attach
            attachToParent(root, rightNode, mid + 1, right);
            stack.push(new int[]{mid + 1, right, rightMid});
        }
    }
    
    return root;
}

Complexity Analysis

Time Complexity: O(n) where n is the length of the array
Space Complexity: O(log n) for the stack

Key Insights

Middle Element as Root: Always choose the middle element to ensure height balance
Divide and Conquer: Split the array into two halves and recursively build subtrees
Height Balance: This approach guarantees a height-balanced tree
BST Property: The resulting tree maintains BST property due to sorted input
Recursive vs Iterative: Both approaches have the same time complexity

Edge Cases

Empty array: Return null
Single element: Return a single node
Two elements: Can form two valid BSTs
Odd length: Middle element is clear
Even length: Choose left middle element

Test Cases

# Test cases
# Example 1: [-10,-3,0,5,9] -> height-balanced BST
# Example 2: [1,3] -> [3,1] or [1,null,3]
# Example 3: [1] -> [1]
# Example 4: [] -> null

Follow-up Questions

Convert BST to Sorted Array: Reverse operation
Balance Existing BST: Balance an already constructed BST
Multiple Arrays: Convert multiple sorted arrays to BSTs
Custom Balance: Create BST with specific balance criteria
Range Queries: Add range query functionality to the BST

Common Mistakes

Wrong middle calculation: Using (left + right) / 2 instead of left + (right - left) / 2
Index bounds: Not handling empty arrays or invalid ranges
Parent linking: Not properly linking parent and child nodes
Stack overflow: Deep recursion on large arrays
Memory allocation: Creating unnecessary temporary arrays

Interview Tips

Start with examples: Walk through the conversion process
Explain balance: Clarify what height-balanced means
Discuss approaches: Compare recursive vs iterative solutions
Handle edge cases: Always consider empty and single element cases
Optimize space: Mention the space complexity benefits of iterative approach

Variations

Custom Balance Factor: Allow different balance criteria
Multiple Roots: Create multiple BSTs from array segments
In-place Construction: Build BST without extra space
Lazy Construction: Build BST nodes on-demand
Parallel Construction: Build subtrees in parallel