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.
Build and Validate a BST: Rebuild from preorder
Next is 30. It is smaller than 50 on top of the stack, so it is the left child of 50. Push it.
Cost
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n)
- Space
- O(h)
Before this
Taught by the same lesson
Build and Validate a BST covers these too, in the same run.