# Nodes in a binary search tree that span a range

I have a binary search tree of height $$h$$ with an integer in each leaf. I also have a range $$[\ell,u]$$. I want to find a set of nodes that span the range $$[\ell,u]$$, i.e., a set $$S$$ of nodes such that the leaves under $$S$$ form all (and only) those leaves containing integers in the range $$[\ell,u]$$. How large does $$S$$ need to be, in the worst case, as a function of the height $$h$$? How do I find such a set explicitly?

I'm assuming you have parent pointers, you can probably avoid them by maintaining a couple stacks though.

Find the extremal two nodes $$\ell \leq p \leq q \leq u$$ and their common ancestor $$a$$ in $$O(h)$$ time. If nodes $$p$$ and $$q$$ are the same, return $$S = \{p\}$$.

While $$p$$ is the left child of its parent and its parent is not the common ancestor, let $$p := \text{parent}(p)$$. Similarly for $$q$$ but with being the right child as criterion.

Now if $$p$$ and $$q$$ are both the direct children of $$a$$ let $$S = \{a\}$$ and you are done. Otherwise initialize $$S = \{p, q\}$$ and repeat:

1. $$p := \text{parent}(p)$$
2. If $$p = a$$ break.
3. Add the right child of $$p$$ to $$S$$.

And to finish up, do the same for $$q$$ but adding the left children instead. Note that the first iteration of the above loop can add $$p$$ or $$q$$ to the set while it is already in it. If you use an array instead of a proper set you want to make a special case for the first iteration.

In the worst case this adds $$2h + O(1)$$ elements to $$S$$. This can be necessary too, consider a full binary tree where the range includes all but the smallest and biggest node.