Where it runs
1. The problem
In the last lesson you built a search tree by inserting values, so the order rule held on its own. Now a tree comes from outside: from a loaded file, from an index another program wrote, from merging two trees. Before you trust it, you have to check: is it really a search tree, smaller on the left and larger on the right at every node?
If it isn't, a search on such a tree will quietly return wrong answers. Search relies on the rule and drops whole subtrees without looking into them.
Once you can trust the tree, a second question comes up: which value is third, counting from the smallest? Which one is in the middle (the median)? You want the k-th value in order without collecting all the values and sorting them.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedOn LeetCode
Problems that check or use the order of a binary search tree as a whole. Carry low and high bounds down, or walk inorder, which reads the values in sorted order.
The lesson's isValidBST, with bounds checked at every node and not only against the parent.
The lesson's kthSmallest, stopping the inorder walk after k nodes.
Inorder gives sorted values, so the answer is the smallest gap between neighbours in that walk.
In the inorder walk find the one or two places where a value drops, and swap the two nodes out of order.