Print Every Value Smaller Than a Limit
Print Every Value Smaller Than a Limit
Complete print_smaller_than(const MinHeap *heap, int i, int limit). It prints every value smaller than limit in the part of the tree that starts at index i, each as a space followed by the number, in pre-order. It is recursive: after its own value it calls itself on the left child, then on the right child.
Reminder: why a min heap lets you skip whole branches. A min heap is a complete binary tree kept in an array, filled row by row, left to right, with no gaps, and every parent is smaller than or equal to its children. Follow that rule downward and every value under a node is at least as big as the node itself, so once a node is not smaller than the limit, nothing below it can be either, and the whole branch can be skipped. It is NOT a binary search tree: a small value can sit on either side, so both children have to be visited.
print_smaller_than(heap, 0, 7) on this heap:
index: 0 1 2 3 4 5 6 7
value: 2 4 3 9 5 8 6 10
2 printed 1st
/ \
4 3 4 printed 2nd, 3 printed 4th
/ \ / \
[9] 5 [8] 6 5 printed 3rd, 6 printed 5th
/
10 under [9], so never visited
[9] and [8] are not smaller than 7: the call stops there and goes no deeper
visiting order: 2, 4, [9], 5, 3, [8], 6
printed: 2 4 5 3 6Pre-order means this node first, then its whole left subtree, then its whole right subtree. That is why 5 comes out before 3, even though 3 is earlier in the array. A child index at or past heap->size is not a node at all, so a call made with it just returns.
Requirements:
1. If i is at or past heap->size, return without printing. This is how the recursion stops below a leaf.
2. If the value at i is greater than or equal to limit, return without printing and without visiting its children: everything below it is at least as big.
3. Otherwise print the value as " %d" (a space, then the number, no newline), then call print_smaller_than on the left child, then on the right child.
4. The runner prints the Smaller than ...: label, calls print_smaller_than(heap, 0, limit) and ends the line itself. An empty heap, or a root that is not smaller than the limit, prints nothing.
5. Print in pre-order, not in array order, and do not change the heap.
Do NOT write a main function.
Expected Output:
MinHeap: 1 4 2 6 5 3 9 7 8 10 Smaller than 6: 1 4 5 2 3 Smaller than 9: 1 4 6 7 8 5 2 3 Smaller than 1: Smaller than 100: 1 4 6 7 8 5 10 2 3 9
= newline. The output ends with a newline — print one after the last line.
Your Output
Run your code to see the output here...