Topic 10 of 20
Use the ordering invariant: inorder is sorted, and every step discards a subtree.
A binary search tree keeps every value in a node's left subtree smaller than the node and every value in the right subtree larger. That single invariant gives you two superpowers. You can search, insert and delete in O(h) time by going left or right at each step. And an inorder traversal visits the values in sorted order.
Most BST interview questions are really asking you to exploit one of those properties. Validating a BST means passing down the allowed (min, max) range. Finding the k-th smallest means stopping an inorder traversal early. Converting a sorted array into a balanced BST means always choosing the middle element as the root.
Remember that h is O(log n) only for balanced trees and O(n) in the worst case. Production code uses self-balancing trees (red-black, AVL) exposed as ordered sets and maps, such as TreeMap in Java or std::set in C++. The last problems here use them to answer "nearest value" queries efficiently.
Walk left or right; the O(h) search every BST operation builds on.
Skipping subtrees that fall outside the range.
Choosing the middle element produces a balanced BST.
Adjacent inorder values give the minimum difference.
Two Sum on a tree, via a sorted inorder list or a hash set.
Passing (min, max) bounds down; one of the most-asked tree problems.
Early-stopping inorder traversal.
LCA becomes a simple walk thanks to ordering.
Recursive insertion that preserves the invariant.
Deletion with the inorder successor; tests case analysis.
Lazy inorder with a stack in O(h) memory.
Bounds-based construction in O(n).
Finding two swapped nodes via inorder anomalies.
Ordered-set or bucket window for nearby-value queries.
Return BST validity, bounds and sum from each subtree.