Is there an Interval Tree which supports O(1) dynamic space requirements for queries?

Question

I observed that all the interval tree implementations I am able to come up with are required to utilize a stack (or a-like) to answer queries (report any overlapping interval with a key).

In general when visiting a node in an (common) interval tree you are required to visit multiple child nodes and check for results there and recurse. This requires you to (dynamically) allocate memory upon lookup.

In contrast, f.e. consider a simple binary search tree. You can easily unroll the recursion because you will only ever visit a single child node.

Is it possible to achieve a similar algorithm for intervals? To clarify I would like to know whether there exists an interval tree which supports finding any overlapping interval in constant required space.

Answer 1

Short answer yes, you can achieve this in any type of tree, if there is a pointer from child to parent node.

The purpose of the stack is to remember you have to go back and visit another branch. Without the stack, but with the ability to go back to parent nodes, you can check if there is another branch that you should have visited.

Then the only space you need is 1 node. The query time might be slightly longer, although still log(n). The stack is an optimization, and after you remove it, you need an extra while loop to go back and check the latest other branch.