BST Reconstruction from Preorder
Keep a stack of nodes with an open right side; a smaller value is the top's left child, a larger one the right child of the last node popped.
Next is 30. It is smaller than 50 on top of the stack, so it is the left child of 50. Push it.
What you will see
Values are consumed left to right and placed by their allowed interval.
Cost
| Best | O(n) |
|---|---|
| Average | O(n) |
| Worst | O(n) |
| Space | O(h) |
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.