AlgoScope

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.

Tree algorithms, algorithm, advanced
30 is the left child of 50.3050
30 is the left child of 50.3050

Build and Validate a BST: Rebuild from preorder

Decision, step 3 of 9

Next is 30. It is smaller than 50 on top of the stack, so it is the left child of 50. Push it.

How build and validate a bst works

Cost

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

Taught by the same lesson

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