4
$\begingroup$

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?

| cite | improve this question | | | | |
$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.