AlgoScope

BST from Sorted Array

Take the middle as the root and recurse on both halves, for a tree of height log n.

Tree algorithms, algorithm, intermediate
4 becomes a node at depth 0.4current
4 becomes a node at depth 0.4current

Build and Validate a BST: Seven sorted values, balanced

Decision, step 2 of 9

Indices 0 to 6: the middle is index 3, 4. It is the root. Everything before it goes left, everything after goes right.

Cost

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(log n)

Taught by the same lesson

Build and Validate a BST covers these too, in the same run.