Recursion and Trees
Search trees and the ordering you can exploit
Three problems that all collapse once you take the ordering property seriously.
Key idea
The property, stated carefully
In a binary search tree, everything in a node's left subtree is smaller than the node, and everything in its right subtree is larger. Note the word everything: the promise is about entire subtrees, not just about immediate children.
That distinction is the source of the most common wrong answer in this whole unit, and the validation problem below is built on it.
Why it works
Validation carries a range downward
Checking each node against its children is not enough. Each node must be checked against a range of values it is allowed to hold, and that range narrows as you descend.
The root may hold anything. Moving left tightens the upper bound to the parent's value; moving right tightens the lower bound. This is the carry-down pattern from the last lesson, with two pieces of context instead of one.
Below, the narrowing is done along one chosen path rather than over the whole tree, so that the window itself is the thing on display.
Tip
Turning the walk into a recursion
The function above follows one path because a path is easy to look at. A validator has to check every path, and it gets that for free by passing the narrowed window down to both children instead of choosing one.
Two details decide whether it is correct. The comparisons have to be strict, since a value equal to a bound would break the ordering. And the root's window has to be genuinely unbounded rather than a large number, because the values in the tree may be larger than whatever you picked.
Key idea
Searching takes one path, not a traversal
The ordering means a search never has to look at both children. Compare the target with the node and descend into the only side that could contain it.
That is O(h) rather than O(n), and h is about log n for a balanced tree. Any BST problem where you find yourself traversing everything deserves a second look, because the ordering usually rules out most of the tree.
Tip
Where two targets separate
A useful consequence: given two values, the first node from which they descend in different directions is the deepest node that has both beneath it.
So a loop that walks down while both targets are on the same side, and stops the moment they diverge, answers a common question in O(h) with no recursion and no extra space. Working out why the stopping point is correct is worth doing before you use it.
Why it works
In-order traversal is sorted
Visit the left subtree, then the node, then the right subtree, and the values come out in ascending order. That follows directly from the ordering property and it is the single most useful fact about search trees.
It turns questions about rank and order into questions about position in a sorted sequence. The kth smallest value is the kth thing this traversal produces, so the traversal can stop as soon as it has produced k, without visiting the rest.
Tip
Building the whole list is usually wasteful
The version above allocates a list at every node, which is O(n) space and does more work than necessary when you only want a prefix of the result.
An iterative in-order walk with an explicit stack produces values one at a time and can stop the moment it has enough. That is the shape the third problem below wants, and it is also the answer to the follow-up about what happens when the tree is modified often.
Why is checking children not enough?
A candidate validates a search tree by checking, at every node, that its left child is smaller and its right child is larger. What does this miss?
Validate Binary Search Tree
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.
Lowest Common Ancestor Of A Binary Search Tree
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.
Kth Smallest Element In A Bst
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.