# Range search in a max-heap

I am having trouble with coming up for a suitable algorithm for this question. A max-heap is essentially visualized as a binary tree not a binary search tree. Also the runtime of the algorithm must depend only on the number of elements in the output. I was thinking of doing a preorder traversal on the max heap. While doing the preorder traversal, if the value of a node is less than the given value x, we return to the previous recursive call. All child nodes in a max heap are less than the parent node. Otherwise we output current node and recur on the children.

I am not sure however if the runtime of this algorithm depends only on the number of elements in the output.

Anybody have other suggestions/thoughts? Thanks.

• Please credit the original source for where you encountered this. Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics using LaTeX.
– D.W.
Commented Aug 6, 2020 at 4:52
• – D.W.
Commented Aug 6, 2020 at 4:53
• (Do you need a full pre-order traversal?) Commented Aug 7, 2020 at 3:41

## 1 Answer

The algorithm you're describing is basically correct.

To summarize in one sentence: "If the current value is less than $$x$$, turn back."

The reason it has the desired time complexity is because the set of the nodes you are visiting is precisely:

• the root node
• all the nodes which are direct descendants of the nodes in the output (since every node has no more than two children, there are no more than $$2k$$ of these)

So the total number of times the body of your function gets executed is no more than $$2k+1$$.

• I see! Thank you for clarifying. Commented Aug 6, 2020 at 0:11