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:

• $p := \text{parent}(p)$

• If $p = a$ break.

• 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.

StackExchange Computer Science Q#111555, answer score: 2