BST from Sorted Array
Take the middle as the root and recurse on both halves, for a tree of height log n.
Decision · step 2 of 9Build and Validate a BST: Seven sorted values, balanced
Indices 0 to 6: the middle is index 3, 4. It is the root. Everything before it goes left, everything after goes right.
What you will see
The array's middle lifts up to become a node; halves recurse below it.
Cost
| Best | O(n) |
|---|---|
| Average | O(n) |
| Worst | O(n) |
| Space | O(log n) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next, try operations in any order.
Screen readers: Nodes announce value, left child and right child; each step announces the comparison and the direction taken or the structural change.
Reduced motion: Focus jumps node to node with a static ring; rotations become a crossfade between the two layouts.
Before this
Taught by the same lesson
Build and Validate a BST covers these too, in the same run.