Range search in a max-heap


Question

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.