Convert Sorted Array to Binary Search Tree
Easy · Trees · Explanation and code example
Iterative DFS
How it works
The recursive approach can be converted to an iterative one using an explicit stack. We store pending work items on the stack, where each item contains a node to be filled and the array bounds it should use. This simulates the recursive call stack and processes each subtree systematically without recursion.
Steps
- If the array is empty, return
null. - Create a root node with a placeholder value.
- Push the root node along with its bounds
(0, n-1)onto a stack. - While the stack is not empty:
- Pop an item containing the node and its bounds
(l, r). - Calculate the middle index and set the node's value to
nums[mid]. - If there are elements to the left (
l <= mid - 1), create a left child and push it with bounds(l, mid - 1). - If there are elements to the right (
mid + 1 <= r), create a right child and push it with bounds(mid + 1, r).
- Pop an item containing the node and its bounds
- Return the root.
Complexity
- Time complexity:
O(n) - Space complexity:
O(log n)space for the stack.O(n)space for the output.
Things to watch for
Off-by-One Errors in Subarray Bounds
When recursively building subtrees, a common mistake is including the middle element in one of the subarrays, leading to infinite recursion or duplicate nodes.
Choosing Wrong Middle Element in Even-Length Arrays
For arrays with even length, the middle can be either (l + r) // 2 or (l + r + 1) // 2. While both produce valid height-balanced BSTs, inconsistency can cause confusion. The problem accepts either choice, but stick with one consistently.
Python code example
from typing import List
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if not nums:
return None
root = TreeNode(0)
stack = [(root, 0, len(nums) - 1)]
while stack:
node, l, r = stack.pop()
m = (l + r) // 2
node.val = nums[m]
if l <= m - 1:
node.left = TreeNode(0)
stack.append((node.left, l, m - 1))
if m + 1 <= r:
node.right = TreeNode(0)
stack.append((node.right, m + 1, r))
return root
C++ code example
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
if (nums.empty()) return nullptr;
TreeNode* root = new TreeNode(0);
stack<tuple<TreeNode*, int, int>> stack;
stack.push({root, 0, (int)nums.size() - 1});
while (!stack.empty()) {
auto [node, l, r] = stack.top();
stack.pop();
int m = (l + r) / 2;
node->val = nums[m];
if (l <= m - 1) {
node->left = new TreeNode(0);
stack.push({node->left, l, m - 1});
}
if (m + 1 <= r) {
node->right = new TreeNode(0);
stack.push({node->right, m + 1, r});
}
}
return root;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.