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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
