Log inSign up
easyLeetCodeNot Started

Convert Sorted Array to Binary Search Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

BST
Solve on LeetCode
Lesson

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.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Construct height-balanced BSTs in optimal O(N) time from sorted sequences.
  • Prevent integer overflow in midpoint calculations.
  • Understand why binary splitting guarantees height <= ceil(log2(N + 1)).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Sorted array to balanced BST.
  • Minimal height binary tree construction.
  • Divide and conquer on array ranges.

Algorithmic Decision Tree:

  • Pick mid = L + (R - L) / 2 as root.
  • root.left = build(L, mid - 1), root.right = build(mid + 1, R).

Connected Patterns:

Convert Sorted List to Binary Search TreeBalance a Binary Search TreeBinary Search

1. Sequential BST Insertion

Intuition

Inserting elements from an already-sorted array sequentially into a standard BST creates a completely degenerate right-skewed tree (linked list) of height N, resulting in O(N2) insertion time and O(N) search depth.

When to apply: Naive baseline demonstrating why unbalanced insertion fails.

Algorithm

  1. Step 1: Create root with nums[0].
  2. Step 2: Loop i from 1 to N - 1, call standard BST insert.
  3. Step 3: Result is unbalanced with height N.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5struct TreeNode {
6 int val;
7 TreeNode *left, *right;
8 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9};
10
11class Solution {
12 TreeNode* insert(TreeNode* root, int val) {
13 if (!root) return new TreeNode(val);
14 if (val < root->val) root->left = insert(root->left, val);
15 else root->right = insert(root->right, val);
16 return root;
17 }
18public:
19 TreeNode* sortedArrayToBST(vector<int>& nums) {
20 if (nums.empty()) return nullptr;
21 TreeNode* root = new TreeNode(nums[0]);
22 for (size_t i = 1; i < nums.size(); i++) insert(root, nums[i]);
23 return root;
24 }
25};
26
27int main() {
28 vector<int> nums = {-10, -3, 0, 5, 9};
29 Solution sol;
30 TreeNode* root = sol.sortedArrayToBST(nums);
31 cout << "Root: " << root->val << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(N^2)
  • Space complexity: O(N) skewed tree depth

2. Array Slicing Divide-and-Conquer

Intuition

Pick mid = len(nums) // 2 as root. Recursively pass sliced arrays nums[:mid] for left child and nums[mid+1:] for right child. While conceptually correct, copying array slices takes O(N) time at each level, resulting in O(N log N) total time and extra O(N log N) memory.

When to apply: Quick prototype in high-level languages like Python.

Algorithm

  1. Step 1: If array empty, return null.
  2. Step 2: mid = len / 2, root = TreeNode(nums[mid]).
  3. Step 3: root.left = build(nums[:mid]), root.right = build(nums[mid+1:]).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5struct TreeNode {
6 int val;
7 TreeNode *left, *right;
8 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9};
10
11class Solution {
12public:
13 TreeNode* sortedArrayToBST(vector<int> nums) {
14 if (nums.empty()) return nullptr;
15 int mid = nums.size() / 2;
16 TreeNode* root = new TreeNode(nums[mid]);
17 vector<int> leftSlice(nums.begin(), nums.begin() + mid);
18 vector<int> rightSlice(nums.begin() + mid + 1, nums.end());
19 root->left = sortedArrayToBST(leftSlice);
20 root->right = sortedArrayToBST(rightSlice);
21 return root;
22 }
23};
24
25int main() {
26 vector<int> nums = {-10, -3, 0, 5, 9};
27 Solution sol;
28 TreeNode* root = sol.sortedArrayToBST(nums);
29 cout << "Root: " << root->val << endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(N log N)
  • Space complexity: O(N log N) slicing copies

3. In-Place Index Range Divide-and-Conquer (O(N) Time, O(log N) Space)

Intuition

Define a recursive helper build(L, R) where L and R are boundary indices within the original immutable array. If L > R, return null. Calculate mid = L + (R - L) / 2. Construct root = TreeNode(nums[mid]). Recursively attach root.left = build(L, mid - 1) and root.right = build(mid + 1, R). This avoids all array copying, taking linear O(N) time and O(log N) recursion stack space.

When to apply: The industry standard optimal solution.

Algorithm

  1. Step 1: Define build(L, R): if L > R, return null.
  2. Step 2: Compute mid = L + (R - L) / 2.
  3. Step 3: root = new TreeNode(nums[mid]).
  4. Step 4: root.left = build(L, mid - 1).
  5. Step 5: root.right = build(mid + 1, R).
  6. Step 6: Return root.

Convert Sorted Array Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Array [-10, -3, 0, 5, 9]
Visual state
Values and pointers at this exact step
tree
This tree trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Decision / next transition
Step 1
Why this step matters

Array [-10, -3, 0, 5, 9]. mid = 2 -> root 0 created.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5struct TreeNode {
6 int val;
7 TreeNode *left, *right;
8 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9};
10
11class Solution {
12 TreeNode* build(const vector<int>& nums, int l, int r) {
13 if (l > r) return nullptr;
14 int mid = l + (r - l) / 2;
15 TreeNode* root = new TreeNode(nums[mid]);
16 root->left = build(nums, l, mid - 1);
17 root->right = build(nums, mid + 1, r);
18 return root;
19 }
20public:
21 TreeNode* sortedArrayToBST(vector<int>& nums) {
22 return build(nums, 0, (int)nums.size() - 1);
23 }
24};
25
26int main() {
27 vector<int> nums = {-10, -3, 0, 5, 9};
28 Solution sol;
29 TreeNode* root = sol.sortedArrayToBST(nums);
30 cout << "Optimal Root: " << root->val << ", Left: " << root->left->val << ", Right: " << root->right->val << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(log N) call stack

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Sequential InsertionO(N^2)O(N)Standard BST insert in loop.Unbalanced tree depth.
2.Array SlicingO(N log N)O(N log N)Pass subarray slices.Subarray copying.
3.In-Place Range (Optimal)OptimalO(N)O(log N)Pass L and R bounds into helper.None. This is optimal.

Common Pitfalls & Crucial Edge Cases

Integer overflow in midpoint calculation

Writing (l + r) / 2 can overflow in languages like C++/Java if indices are large. Always write l + (r - l) / 2.

Array slicing in performance-critical code

nums.slice() or nums[:] wastes O(N) memory per level.

Off-by-one in child boundaries

Left child must be build(l, mid - 1) and right child build(mid + 1, r). Including mid again causes infinite recursion.

Crucial Edge Cases to Validate:

  • Single element array `[5]` — Returns a single root node with no children.
  • Two element array `[1, 2]` — Root 1 with right child 2 (or root 2 with left child 1). Height difference is 1, which is valid.
  • Array with negative numbers — Handled naturally without sign bugs.
  • Large input (N = 10^4) — Runs in milliseconds with O(log N) recursion depth.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the divide-and-conquer invariant: 'By choosing mid, left subtree size and right subtree size differ by at most 1.'
  2. Mention that this is identical to binary search tree building and is the base pattern for 'Convert Sorted List to BST'.
  3. Highlight the O(log N) stack space guarantee.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does choosing the middle element of the sorted array guarantee that the resulting BST is height-balanced?

2.What is the maximum height of the binary search tree created by this algorithm for N = 104 nodes?

3.Is there only ONE unique valid height-balanced BST for a given sorted array?

Back to DSA Sheet