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 one.

What to notice first

• Divide and conquer: Pick the middle element as the root to balance the tree.
• Recursively build left and right subtrees from the left and right halves.
• The sorted order guarantees BST property without additional checking.
• Any array element can be the root; the middle pick ensures balance.

Examples

Input	Output
nums = [-10,-3,0,5,9]	A balanced BST with root 0, left child -3, right child 5
nums = [1,3]	A balanced BST with root 3, left child 1

Constraints

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

Real-World Applications

Where this pattern appears

• Database indexing — balanced BSTs are used for efficient lookups and range queries.
• Memory allocation — divide and conquer builds balanced data structures.
• Game AI — balanced trees for decision trees and minimax algorithms.
• Networking — balanced routing trees for efficient packet forwarding.
• Configuration systems — hierarchical data structures for settings management.

Complexity Comparison

Approach	Time	Space
Recursive	O(n)	O(log n)
Iterative	O(n)	O(n)

Space is for recursion stack (recursive) or queue (iterative)

Which approach should you learn first?

• Pick Recursive for clarity — divide and conquer pattern is intuitive.
• Pick Iterative if you prefer avoiding recursion or want explicit queue management.

Intuitive Pattern

Recursive

O(n) time · O(log n) space

Bottom-up Build

Iterative

O(n) time · O(n) space

Approach 1: Recursive Divide and Conquer (Recommended)

★ Recommended

1. Find the middle element of the current range → becomes the root.
2. Recursively build the left subtree from the left half.
3. Recursively build the right subtree from the right half.
4. Base case: when left > right, return null.

⏱ Time O(n) Visit each node once 💾 Space O(log n) Recursion depth

Pseudocode

function sortedArrayToBST(nums):
    return build(0, len(nums) - 1)

function build(left, right):
    if left > right:
        return null

    mid = (left + right) / 2
    root = TreeNode(nums[mid])
    root.left = build(left, mid - 1)
    root.right = build(mid + 1, right)
    return root

Solution Code

Python

convert_sorted_array_bst_recursive.py

from typing import Optional, List


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


def sortedArrayToBST(nums: List[int]) -> Optional[TreeNode]:
    def build(left: int, right: int) -> Optional[TreeNode]:
        if left > right:
            return None

        mid = (left + right) // 2
        root = TreeNode(nums[mid])
        root.left = build(left, mid - 1)
        root.right = build(mid + 1, right)
        return root

    return build(0, len(nums) - 1)


# Example usage
nums = [-10, -3, 0, 5, 9]
root = sortedArrayToBST(nums)
print(root.val)  # 0
print(root.left.val)  # -3
print(root.right.val)  # 5

C++

convert_sorted_array_bst_recursive.cpp

#include <iostream>
#include <vector>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* sortedArrayToBST(std::vector<int>& nums, int left, int right) {
    if (left > right) return nullptr;

    int mid = left + (right - left) / 2;
    TreeNode* root = new TreeNode(nums[mid]);
    root->left = sortedArrayToBST(nums, left, mid - 1);
    root->right = sortedArrayToBST(nums, mid + 1, right);
    return root;
}

TreeNode* sortedArrayToBST(std::vector<int>& nums) {
    return sortedArrayToBST(nums, 0, nums.size() - 1);
}

int main() {
    std::vector<int> nums = {-10, -3, 0, 5, 9};
    TreeNode* root = sortedArrayToBST(nums);
    std::cout << root->val << std::endl;  // 0
    std::cout << root->left->val << std::endl;  // -3
    std::cout << root->right->val << std::endl;  // 5
    return 0;
}

Java

ConvertSortedArrayToBST_Recursive.java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }

    private TreeNode build(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 = build(nums, left, mid - 1);
        root.right = build(nums, mid + 1, right);
        return root;
    }
}

public class ConvertSortedArrayToBST_Recursive {
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {-10, -3, 0, 5, 9};
        TreeNode root = sol.sortedArrayToBST(nums);
        System.out.println(root.val);  // 0
        System.out.println(root.left.val);  // -3
        System.out.println(root.right.val);  // 5
    }
}

JavaScript

convert_sorted_array_bst_recursive.js

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

function sortedArrayToBST(nums) {
    function build(left, right) {
        if (left > right) return null;

        const mid = Math.floor((left + right) / 2);
        const root = new TreeNode(nums[mid]);
        root.left = build(left, mid - 1);
        root.right = build(mid + 1, right);
        return root;
    }

    return build(0, nums.length - 1);
}

// Example usage
const nums = [-10, -3, 0, 5, 9];
const root = sortedArrayToBST(nums);
console.log(root.val);  // 0
console.log(root.left.val);  // -3
console.log(root.right.val);  // 5

Rust

convert_sorted_array_bst_recursive.rs

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

fn sorted_array_to_bst(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
    fn build(nums: &Vec<i32>, left: usize, right: i32) -> Option<Rc<RefCell<TreeNode>>> {
        if left as i32 > right {
            return None;
        }

        let mid = left + ((right as usize - left) / 2);
        let mut node = TreeNode::new(nums[mid]);
        node.left = build(nums, left, mid as i32 - 1);
        node.right = build(nums, mid + 1, right);

        Some(Rc::new(RefCell::new(node)))
    }

    if nums.is_empty() {
        None
    } else {
        build(&nums, 0, nums.len() as i32 - 1)
    }
}

fn main() {
    let nums = vec![-10, -3, 0, 5, 9];
    let root = sorted_array_to_bst(nums);
    if let Some(r) = root {
        println!("{}", r.borrow().val);  // 0
    }
}

Go

convert_sorted_array_bst_recursive.go

package main

import "fmt"

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

func sortedArrayToBST(nums []int) *TreeNode {
  var build func(int, int) *TreeNode
  build = func(left, right int) *TreeNode {
    if left > right {
      return nil
    }

    mid := left + (right-left)/2
    root := &TreeNode{Val: nums[mid]}
    root.Left = build(left, mid-1)
    root.Right = build(mid+1, right)
    return root
  }

  return build(0, len(nums)-1)
}

func main() {
  nums := []int{-10, -3, 0, 5, 9}
  root := sortedArrayToBST(nums)
  fmt.Println(root.Val)  // 0
  fmt.Println(root.Left.Val)  // -3
  fmt.Println(root.Right.Val)  // 5
}

Approach 2: Iterative with Queue

🎯 Interview Favourite

Use a queue to track (node, left, right) tuples. Process each node by assigning its value and enqueueing children if ranges are valid.

⏱ Time O(n) Visit each node once 💾 Space O(n) Queue storage

Solution Code

Python

convert_sorted_array_bst_iterative.py

from typing import Optional, List
from collections import deque


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


def sortedArrayToBST(nums: List[int]) -> Optional[TreeNode]:
    if not nums:
        return None

    root = TreeNode()
    queue = deque([(root, 0, len(nums) - 1)])

    while queue:
        node, left, right = queue.popleft()

        mid = (left + right) // 2
        node.val = nums[mid]

        if left <= mid - 1:
            node.left = TreeNode()
            queue.append((node.left, left, mid - 1))

        if mid + 1 <= right:
            node.right = TreeNode()
            queue.append((node.right, mid + 1, right))

    return root


# Example usage
nums = [-10, -3, 0, 5, 9]
root = sortedArrayToBST(nums)
print(root.val)  # 0
print(root.left.val)  # -3
print(root.right.val)  # 5

C++

convert_sorted_array_bst_iterative.cpp

#include <iostream>
#include <vector>
#include <queue>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x = 0) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* sortedArrayToBST(std::vector<int>& nums) {
    if (nums.empty()) return nullptr;

    TreeNode* root = new TreeNode();
    std::queue<std::tuple<TreeNode*, int, int>> q;
    q.push({root, 0, (int)nums.size() - 1});

    while (!q.empty()) {
        auto [node, left, right] = q.front();
        q.pop();

        int mid = left + (right - left) / 2;
        node->val = nums[mid];

        if (left <= mid - 1) {
            node->left = new TreeNode();
            q.push({node->left, left, mid - 1});
        }

        if (mid + 1 <= right) {
            node->right = new TreeNode();
            q.push({node->right, mid + 1, right});
        }
    }

    return root;
}

int main() {
    std::vector<int> nums = {-10, -3, 0, 5, 9};
    TreeNode* root = sortedArrayToBST(nums);
    std::cout << root->val << std::endl;  // 0
    std::cout << root->left->val << std::endl;  // -3
    std::cout << root->right->val << std::endl;  // 5
    return 0;
}

Java

ConvertSortedArrayToBST_Iterative.java

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) return null;

        TreeNode root = new TreeNode(0);
        Queue<Object[]> queue = new LinkedList<>();
        queue.offer(new Object[]{root, 0, nums.length - 1});

        while (!queue.isEmpty()) {
            Object[] item = queue.poll();
            TreeNode node = (TreeNode) item[0];
            int left = (int) item[1];
            int right = (int) item[2];

            int mid = left + (right - left) / 2;
            node.val = nums[mid];

            if (left <= mid - 1) {
                node.left = new TreeNode(0);
                queue.offer(new Object[]{node.left, left, mid - 1});
            }

            if (mid + 1 <= right) {
                node.right = new TreeNode(0);
                queue.offer(new Object[]{node.right, mid + 1, right});
            }
        }

        return root;
    }
}

public class ConvertSortedArrayToBST_Iterative {
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {-10, -3, 0, 5, 9};
        TreeNode root = sol.sortedArrayToBST(nums);
        System.out.println(root.val);  // 0
        System.out.println(root.left.val);  // -3
        System.out.println(root.right.val);  // 5
    }
}

JavaScript

convert_sorted_array_bst_iterative.js

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

function sortedArrayToBST(nums) {
    if (nums.length === 0) return null;

    const root = new TreeNode();
    const queue = [[root, 0, nums.length - 1]];

    while (queue.length > 0) {
        const [node, left, right] = queue.shift();

        const mid = Math.floor((left + right) / 2);
        node.val = nums[mid];

        if (left <= mid - 1) {
            node.left = new TreeNode();
            queue.push([node.left, left, mid - 1]);
        }

        if (mid + 1 <= right) {
            node.right = new TreeNode();
            queue.push([node.right, mid + 1, right]);
        }
    }

    return root;
}

// Example usage
const nums = [-10, -3, 0, 5, 9];
const root = sortedArrayToBST(nums);
console.log(root.val);  // 0
console.log(root.left.val);  // -3
console.log(root.right.val);  // 5

Rust

convert_sorted_array_bst_iterative.rs

use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;

#[derive(Debug)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

fn sorted_array_to_bst(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
    if nums.is_empty() {
        return None;
    }

    let root = Rc::new(RefCell::new(TreeNode::new(0)));
    let mut queue: VecDeque<(Rc<RefCell<TreeNode>>, usize, usize)> = VecDeque::new();
    queue.push_back((Rc::clone(&root), 0, nums.len() - 1));

    while let Some((node, left, right)) = queue.pop_front() {
        let mid = left + (right - left) / 2;
        node.borrow_mut().val = nums[mid];

        if left + 1 <= mid {
            let new_node = Rc::new(RefCell::new(TreeNode::new(0)));
            node.borrow_mut().left = Some(Rc::clone(&new_node));
            queue.push_back((new_node, left, mid - 1));
        }

        if mid + 1 <= right {
            let new_node = Rc::new(RefCell::new(TreeNode::new(0)));
            node.borrow_mut().right = Some(Rc::clone(&new_node));
            queue.push_back((new_node, mid + 1, right));
        }
    }

    Some(root)
}

fn main() {
    let nums = vec![-10, -3, 0, 5, 9];
    let root = sorted_array_to_bst(nums);
    if let Some(r) = root {
        println!("{}", r.borrow().val);  // 0
    }
}

Go

convert_sorted_array_bst_iterative.go

package main

import "fmt"

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

func sortedArrayToBST(nums []int) *TreeNode {
  if len(nums) == 0 {
    return nil
  }

  root := &TreeNode{}
  type state struct {
    node  *TreeNode
    left  int
    right int
  }

  queue := []state{{root, 0, len(nums) - 1}}

  for len(queue) > 0 {
    curr := queue[0]
    queue = queue[1:]

    mid := curr.left + (curr.right-curr.left)/2
    curr.node.Val = nums[mid]

    if curr.left <= mid-1 {
      curr.node.Left = &TreeNode{}
      queue = append(queue, state{curr.node.Left, curr.left, mid - 1})
    }

    if mid+1 <= curr.right {
      curr.node.Right = &TreeNode{}
      queue = append(queue, state{curr.node.Right, mid + 1, curr.right})
    }
  }

  return root
}

func main() {
  nums := []int{-10, -3, 0, 5, 9}
  root := sortedArrayToBST(nums)
  fmt.Println(root.Val)  // 0
  fmt.Println(root.Left.Val)  // -3
  fmt.Println(root.Right.Val)  // 5
}

Common mistakes

Watch for these pitfalls

• Using integer division truncation instead of proper midpoint calculation.
• Forgetting the base case (left > right returns null).
• Building an unbalanced tree by always picking left or right instead of middle.
• Off-by-one errors in left/right pointer updates.
• Creating new TreeNode without assigning a value (then assigning later in iterative).

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

convert_sorted_array_to_binary_search_tree_space_optimized.py

"""
Solution for Convert Sorted Array to Binary Search Tree
"""

def solve():
    """Implementation for approach 3 of Convert Sorted Array to Binary Search Tree"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

convert_sorted_array_to_binary_search_tree_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Convert Sorted Array to Binary Search Tree
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

ConvertSortedArrayToBinarySearchTreeSpaceOptimized.java

/**
 * Solution for Convert Sorted Array to Binary Search Tree
 * Approach 3
 */
public class ConvertSortedArrayToBinarySearchTreeSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

convert_sorted_array_to_binary_search_tree_space_optimized.js

/**
 * Solution for Convert Sorted Array to Binary Search Tree
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

convert_sorted_array_to_binary_search_tree_space_optimized.rs

/// Solution for Convert Sorted Array to Binary Search Tree
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

convert_sorted_array_to_binary_search_tree_space_optimized.go

package main

import "fmt"

// Solution for Convert Sorted Array to Binary Search Tree
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Convert Sorted List to Binary Search Tree ↗ Medium #109
• Balanced Binary Tree ↗ Easy #110
• Unique Binary Search Trees ↗ Medium #96

Interview Tips

Key trade-offs to discuss

• Middle pick: Guarantees height balance; any element works as root if BST property is maintained via sorted input.
• Recursion depth: Log(n) for balanced tree, worst case O(n) for skewed trees (avoided here by middle pick).
• Follow-up: How would you build from an unsorted array? (Sort first, then apply same logic.)
• Space optimization: Can you do it in-place? (Not typical for tree problems; still need O(log n) for recursion.)
• Edge cases: Single element array, two elements, negative numbers, large numbers.

← Previous
#107 Binary Tree Level Order Traversal II Next
#109 Convert Sorted List to Binary Search Tree →