DSA problem
Convert Sorted Array to Binary Search Tree
Given an integer array nums sorted in ascending order, build a height-balanced binary search tree whose inorder traversal recovers nums. A height-balanced tree has the property that the depths of any node's two subtrees differ by at most one.
The construction is a textbook divide-and-conquer in preorder: pick the middle element of the current slice as the root, then recursively build the left subtree from the elements before it and the right subtree from the elements after. Because the array is sorted, this automatically satisfies the BST property (everything left is smaller, everything right is larger). Because we always split in half, the resulting tree is balanced — every node sits at a depth of O(log n).
Implement it with an in-place index-based recursion build(lo, hi) that avoids array copies. When lo > hi return null. Otherwise compute mid = lo + (hi - lo) / 2 (this form is overflow-safe in languages with bounded ints), make a node from nums[mid], set its left child to build(lo, mid - 1), and its right child to build(mid + 1, hi).
Note the order of work: create the root before recursing — this is preorder. Time complexity is O(n) because each element is wrapped in exactly one node; space complexity is O(log n) for the recursion stack (the tree is balanced). Different valid trees can be produced by choosing the left-middle vs. right-middle when the slice has even length; either choice is accepted.
Examples
nums = [-10,-3,0,5,9][0,-3,9,-10,null,5]nums = [1,3][3,1]nums = [0][0]Constraints
- 1 <= nums.length <= 10^4
- -10^4 <= nums[i] <= 10^4
- nums is sorted in strictly increasing order.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.