Skip to main content
Talentd

Convert Sorted Array to Binary Search Tree - Solution & Explanation

EasyArrayDivide and ConquerTreeBinary Search Tree22 min readAsked at: Amazon, Microsoft, Apple +6
Practice this problem

Problem Statement

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 <= 104
  • -104 <= nums[i] <= 104
  • 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.

This C program defines a TreeNode structure and uses a helper function to recursively build the BST from the middle of the array. The recursive calls split the array into two halves to build the left and right subtrees.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of elements in the array, because each element is visited once.

Space Complexity: O(log n) due to the recursion stack in a balanced tree scenario.

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:

  1. If l > r, it means the current array is empty, so return null.
  2. 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.
  3. 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.
  4. 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.
  5. 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.

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Middle Element as Root

Time Complexity: O(n), where n is the number of elements in the array, because each element is visited once.

Space Complexity: O(log n) due to the recursion stack in a balanced tree scenario.

Binary Search + Recursion—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sequential BST InsertionO(n log n) avg, O(n^2) worstO(n)Useful for demonstrating basic BST insertion but does not guarantee a balanced tree
Recursive Middle Element as RootO(n)O(log n)Best choice when the input array is sorted and a height-balanced BST is required

Video Solution

Convert Sorted Array to Binary Search Tree - Leetcode 108 - Python • NeetCode • 114,911 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Convert Sorted Array to Binary Search Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Convert Sorted List to Binary Search Tree