DSA · Trees · #58
Convert Sorted Array to Binary Search Tree
Module 44 · difficulty 2/5·⏱ 30:00starts on first keystroke
Given an integer array `nums` sorted in **strictly increasing** order, build a **height-balanced** binary search tree from its elements. A height-balanced BST is one where the depths of the two subtrees of every node never differ by more than one. Implement `sortedArrayToBST(nums)`. Each tree node is an object `{ val, left, right }` (use `null` for absent children). Return the root node (or `null` for an empty array). Many valid answers exist; any height-balanced BST over `nums` is accepted.
Examples
nums = [-10,-3,0,5,9]→[0,-3,9,-10,null,5]— Picking the middle element (0) as root yields a balanced tree. Other valid layouts exist.nums = [1,3]→[3,1]— Either element may be the root; both produce height-balanced trees.nums = []→[]— An empty array maps to an empty tree (null root).
Constraints
- · 1 <= nums.length <= 10^4 (the empty array is also accepted, returning null)
- · -10^4 <= nums[i] <= 10^4
- · nums is sorted in strictly increasing order
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.