108. Convert Sorted Array to Binary Search Tree Solution

The problem

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

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:

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⁴
-10⁴ <= nums[i] <= 10⁴
nums is sorted in a strictly increasing order.

Approach overview

Problem Overview: You receive a sorted integer array in ascending order and must convert it into a height-balanced Binary Search Tree (BST). The BST property must hold (left < root < right), and the tree height should remain balanced so that operations stay efficient.

Approach 1: Sequential BST Insertion (O(n log n) time, O(n) space)

A straightforward idea is to iterate through the sorted array and insert each value into a BST using standard BST insertion rules. Each insertion places smaller values on the left and larger values on the right. Because the array is already sorted, every new element becomes the right child of the previous node, producing a highly skewed tree that behaves like a linked list.

This approach technically constructs a valid BST, but it fails the height-balanced requirement. Time complexity becomes O(n log n) in the average case but degrades to O(n^2) when the tree becomes completely skewed. Space complexity is O(n) for storing nodes. It demonstrates BST construction basics but does not satisfy the problem constraints.

Approach 2: Recursive Middle Element as Root (O(n) time, O(log n) space)

The optimal strategy leverages the sorted property of the array. The key insight: the middle element naturally divides the array into two equal halves. Choosing the middle element as the root guarantees that the left subtree contains smaller values and the right subtree contains larger values, which preserves the BST property.

From there, recursively build the tree. Pick the middle index mid = (left + right) / 2, create a node with nums[mid], and recursively construct the left subtree from the subarray [left, mid-1] and the right subtree from [mid+1, right]. Each recursive call repeats the same logic until the subarray becomes empty.

This divide-and-conquer pattern ensures the tree remains balanced because each level splits the array roughly in half. Every element becomes a node exactly once, producing O(n) time complexity. The recursion stack depth equals the height of the balanced tree, which is O(log n) space.

This solution directly applies concepts from Divide and Conquer and builds a balanced structure using properties of a Binary Search Tree. The resulting structure is also a valid Binary Tree where subtree heights differ by at most one.

Recommended for interviews: The recursive middle-element approach is what interviewers expect. It shows you recognize how sorted data enables balanced partitioning. Mentioning the naive insertion approach demonstrates understanding of BST construction, but implementing the divide-and-conquer solution shows stronger algorithmic reasoning and leads to the optimal O(n) solution.

Approach 1: Recursive Middle Element as Root

This approach selects the middle element of the current array (or subarray) to ensure a balanced partitioning of elements, thus maintaining the height balance of the BST.

The middle element of the array becomes the root of the BST (or subtree), and the same operation is recursively applied to the left and right halves of the array to form the left and right subtrees respectively.

Python

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

class Solution:
    def sortedArrayToBST(self, nums):
        return self._sortedArrayToBST(nums, 0, len(nums) - 1)

    def _sortedArrayToBST(self, nums, left, right):
        if left > right:
            return None
        mid = (left + right) // 2
        node = TreeNode(nums[mid])
        node.left = self._sortedArrayToBST(nums, left, mid - 1)
        node.right = self._sortedArrayToBST(nums, mid + 1, right)
        return node

Java

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

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

C++

#include <iostream>
#include <vector>

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

TreeNode* sortedArrayToBSTHelper(std::vector<int>& nums, int left, int right) {
    if (left > right) {
        return nullptr;
    }
    int mid = left + (right - left) / 2;
    TreeNode* node = new TreeNode(nums[mid]);
    node->left = sortedArrayToBSTHelper(nums, left, mid - 1);
    node->right = sortedArrayToBSTHelper(nums, mid + 1, right);
    return node;
}

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

JavaScript

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function sortedArrayToBST(nums) {
    function helper(left, right) {
        if (left > right) return null;
        let mid = Math.floor((left + right) / 2);
        let node = new TreeNode(nums[mid]);
        node.left = helper(left, mid - 1);
        node.right = helper(mid + 1, right);
        return node;
    }
    return helper(0, nums.length - 1);
}

#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode* newNode(int value) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

struct TreeNode* sortedArrayToBSTHelper(int* nums, int left, int right) {
    if (left > right) {
        return NULL;
    }
    int mid = left + (right - left) / 2;
    struct TreeNode* node = newNode(nums[mid]);
    node->left = sortedArrayToBSTHelper(nums, left, mid - 1);
    node->right = sortedArrayToBSTHelper(nums, mid + 1, right);
    return node;
}

struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {
    return sortedArrayToBSTHelper(nums, 0, numsSize - 1);
}

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode SortedArrayToBST(int[] nums) {
        return SortedArrayToBST(nums, 0, nums.Length - 1);
    }
    
    private TreeNode SortedArrayToBST(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        int mid = left + (right - left) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = SortedArrayToBST(nums, left, mid - 1);
        node.right = SortedArrayToBST(nums, mid + 1, right);
        return node;
    }
}

This Python code uses two functions where one serves as a helper to recurse through the divided parts of the array to build a balanced BST.

Complexity

Time Complexity: O(n) where n is the size of the array.

Space Complexity: O(log n) for recursion in a balanced setup.

Try this approach in the editor

Approach 2: Binary Search + Recursion

We design a recursive function dfs(l, r), which represents that the values of the nodes to be constructed in the current binary search tree are within the index range [l, r] of the array nums. This function returns the root node of the constructed binary search tree.

The execution process of the function dfs(l, r) is as follows:

If l > r, it means the current array is empty, so return null.
If l leq r, take the element at index mid = \lfloor \frac{l + r}{2} \rfloor of the array as the root node of the current binary search tree, where \lfloor x \rfloor denotes the floor function of x.
Recursively construct the left subtree of the current binary search tree, with the root node's value being the element at index mid - 1 of the array. The values of the nodes in the left subtree are within the index range [l, mid - 1] of the array.
Recursively construct the right subtree of the current binary search tree, with the root node's value being the element at index mid + 1 of the array. The values of the nodes in the right subtree are within the index range [mid + 1, r] of the array.
Return the root node of the current binary search tree.

The answer is the return value of the function dfs(0, n - 1).

The time complexity is O(n), and the space complexity is O(log n). Here, n is the length of the array nums.

TypeScript

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function sortedArrayToBST(nums: number[]): TreeNode | null {
    const dfs = (l: number, r: number): TreeNode | null => {
        if (l > r) {
            return null;
        }
        const mid = (l + r) >> 1;
        return new TreeNode(nums[mid], dfs(l, mid - 1), dfs(mid + 1, r));
    };
    return dfs(0, nums.length - 1);
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sortedArrayToBST(nums []int) *TreeNode {
	var dfs func(int, int) *TreeNode
	dfs = func(l, r int) *TreeNode {
		if l > r {
			return nil
		}
		mid := (l + r) >> 1
		return &TreeNode{nums[mid], dfs(l, mid-1), dfs(mid+1, r)}
	}
	return dfs(0, len(nums)-1)
}

Rust

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn sorted_array_to_bst(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        fn dfs(nums: &Vec<i32>, l: usize, r: usize) -> Option<Rc<RefCell<TreeNode>>> {
            if l > r {
                return None;
            }
            let mid = (l + r) / 2;
            if mid >= nums.len() {
                return None;
            }
            let mut node = Rc::new(RefCell::new(TreeNode::new(nums[mid])));
            node.borrow_mut().left = dfs(nums, l, mid - 1);
            node.borrow_mut().right = dfs(nums, mid + 1, r);
            Some(node)
        }
        dfs(&nums, 0, nums.len() - 1)
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Recursive Middle Element as Root	Time Complexity: O(n) where n is the size of the array. Space Complexity: O(log n) for recursion in a balanced setup.
Binary Search + Recursion	–

Approach

Complexity

Recursive Middle Element as Root

Time Complexity: O(n) where n is the size of the array.

Space Complexity: O(log n) for recursion in a balanced setup.

Binary Search + Recursion

–

Complexity analysis

Approach	Time	Space	When to Use
Sequential BST Insertion	O(n log n) avg, O(n^2) worst	O(n)	Useful for demonstrating basic BST insertion but does not guarantee a balanced tree
Recursive Middle Element as Root	O(n)	O(log n)	Best choice when the input array is sorted and a height-balanced BST is required

Frequently asked questions

Is Convert Sorted Array to Binary Search Tree easy or hard?

Convert Sorted Array to Binary Search Tree is categorized as an Easy problem on most coding platforms. The challenge mainly tests understanding of recursion and how the middle element of a sorted array naturally forms the root of a balanced BST.

Convert Sorted Array to Binary Search Tree Python/Java solution

Python and Java implementations typically define a recursive helper function that receives left and right indices. The function calculates the middle index, creates a node, and recursively constructs the left and right subtrees. This pattern produces a balanced BST in O(n) time.

How to solve Convert Sorted Array to Binary Search Tree in O(n)?

Use a recursive divide-and-conquer strategy. Pick the middle element as the root to keep the tree balanced, then recursively build the left subtree from the left half and the right subtree from the right half of the array. Each element is processed once, giving O(n) time complexity.

What is the best approach for Convert Sorted Array to Binary Search Tree?

The recursive middle-element approach is the most efficient method. Select the middle element of the sorted array as the root, recursively build the left subtree from the left half, and the right subtree from the right half. This guarantees a height-balanced BST and runs in O(n) time with O(log n) recursion space.

Is Convert Sorted Array to Binary Search Tree asked at Google/Amazon/Meta?

Convert Sorted Array to Binary Search Tree is a common interview problem used to evaluate understanding of BST properties and divide-and-conquer recursion. Variants of this problem have appeared in interviews at large tech companies including Google, Amazon, and Meta, particularly for roles testing data structure fundamentals.

What data structure is used in Convert Sorted Array to Binary Search Tree?

The problem focuses on constructing a Binary Search Tree from a sorted array. It also relies heavily on recursion and divide-and-conquer techniques to maintain height balance while building the binary tree structure.

What is the time complexity of Convert Sorted Array to Binary Search Tree?

The optimal divide-and-conquer solution runs in O(n) time because each array element becomes a tree node exactly once. The recursion depth corresponds to the height of a balanced BST, which results in O(log n) auxiliary space from the call stack.

Convert Sorted Array to Binary Search Tree solution and explanation

The problem

Approach overview

Approach 1: Recursive Middle Element as Root

Approach 2: Binary Search + Recursion

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Convert Sorted Array to Binary Search Tree solution and explanation

The problem

Approach overview

Approach 1: Recursive Middle Element as Root

Approach 2: Binary Search + Recursion

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems