#108 Convert Sorted Array to Binary Search Tree
the problem
In plain words
Given a strictly increasing array, build a height-balanced BST (subtree heights differ by at most 1 at every node).
in nums = [-10,-3,0,5,9]
out [0,-3,9,-10,null,5]
[0,-10,5,null,-3,null,9] is also accepted.
in nums = [1,3]
out [3,1]
[1,null,3] is also accepted.
- 1 ≤ nums.length ≤ 10⁴
- -10⁴ ≤ nums[i] ≤ 10⁴
- Strictly increasing
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternBuild a tree from traversalsDivide and conquer
The middle element splits the rest into two halves of (almost) equal size. Make it the root and repeat on each half — that's binary search building a tree.
solutions
From brute force to optimal
build(lo, hi): root = nums[mid], left = build(lo, mid − 1), right = build(mid + 1, hi).
- lo > hi → null.
- mid = lo + (hi − lo) / 2.
- Build both halves.
Each element becomes exactly one node.
Recursion depth of a balanced tree (the output itself is O(n)).
class Solution { public TreeNode sortedArrayToBST(int[] nums) { return build(nums, 0, nums.length - 1); } private TreeNode build(int[] nums, int lo, int hi) { if (lo > hi) return null; int mid = lo + (hi - lo) / 2; // middle value: half go left, half go right TreeNode root = new TreeNode(nums[mid]); root.left = build(nums, lo, mid - 1); root.right = build(nums, mid + 1, hi); return root; }}Same splits, but pending (node, lo, hi) tasks wait in a queue.
- Create the root from the middle.
- Poll a task; create its children from the middles of both halves; queue them.
One task per node.
The queue can hold about half the nodes (the last level).
class Solution { /** A pending node and the index range [lo, hi] its subtree must cover. */ record Task(TreeNode node, int lo, int hi) {} public TreeNode sortedArrayToBST(int[] nums) { if (nums.length == 0) return null; Deque<Task> work = new ArrayDeque<>(); TreeNode root = new TreeNode(nums[(nums.length - 1) / 2]); work.offer(new Task(root, 0, nums.length - 1)); while (!work.isEmpty()) { Task t = work.poll(); int mid = t.lo() + (t.hi() - t.lo()) / 2; // t.node holds nums[mid] if (t.lo() <= mid - 1) { int m = t.lo() + (mid - 1 - t.lo()) / 2; t.node().left = new TreeNode(nums[m]); work.offer(new Task(t.node().left, t.lo(), mid - 1)); } if (mid + 1 <= t.hi()) { int m = mid + 1 + (t.hi() - mid - 1) / 2; t.node().right = new TreeNode(nums[m]); work.offer(new Task(t.node().right, mid + 1, t.hi())); } } return root; }}in the room
How to say it in the interview
talk track
- Say why the middle keeps it balanced: both halves differ in size by at most 1, at every level.
traps
- Inserting the values one by one in sorted order: valid BST, but a degenerate stick — not height-balanced.
what they ask next
Follow-ups
Convert Sorted List to BST (LC 109)?
Either copy to an array, or build by inorder position: recurse on the left half's size, take the current list node as root, advance, recurse right — O(n).
before you submit
Edge cases to test
- One element → a single node.
- Even length → either middle works; both trees are height-balanced.
- 10⁴ elements → the recursion is only about log₂ 10⁴ ≈ 14 calls deep.
practise next
Similar problems
- #105Construct Binary Tree from Preorder and Inorder TraversalMediumin Tree Recursion
- #110Balanced Binary TreeEasyin Tree Recursion
- #704Binary SearchEasyin Binary Search