Print the Path From a Node Up to the Root
Print the Path From a Node Up to the Root
Complete print_path_to_root(heap, i). It prints the value at index i, then its parent, then that parent's parent, and keeps climbing until it has printed the root, all on one line that starts with Path:.
Reminder: every node has exactly one way up. A min heap is a complete binary tree kept in an array, filled row by row, left to right, with no gaps. Every node except the root has exactly one parent, at index (i - 1) / 2, and the root sits at index 0. Every parent is smaller than or equal to its children, so the smallest value is at index 0.
index: 0 1 2 3 4 5 6 7 8
value: 1 4 2 9 5 3 7 12 10
[1]
/ \
[4] 2
/ \ / \
[9] 5 3 7
/ \
[12] 10
[ ] marks the path from index 7 up to the root
index value
start 7 12
parent of 7 3 9 (7 - 1) / 2 = 3
parent of 3 1 4 (3 - 1) / 2 = 1
parent of 1 0 1 (1 - 1) / 2 = 0, the root, so stopStarting at index 7, the function prints Path: 12 9 4 1. Each step up lands on a parent, and a parent is never bigger than its child, so the numbers on the line never grow: they shrink or stay equal until they reach the smallest value in the heap. A value that bubbles up after an insert climbs this same route, but it can stop part way, as soon as its parent is not bigger.
Requirements:
1. Print Path:, then the value at index i, then each value above it, each with one space before it, and end the line with a newline. The last value on the line is the root. No space at the end of the line.
2. Climb with get_parent_index and stop after printing index 0. Watch out at the top: get_parent_index(0) is (0 - 1) / 2, and C rounds that toward zero, so it gives 0, not -1. The index never goes below 0, so a loop that waits for it to go negative never ends: stop once you have printed index 0.
3. i is always a valid index, from 0 to heap->size - 1. When i is 0 the line holds only the root, for example Path: 1.
4. Do not change the heap. Leave the struct, heap_load, get_parent_index and heap_print as they are.
Do NOT write a main function.
Expected Output:
MinHeap: 3 5 8 6 9 10 12 11 7 14 13 from index 8: Path: 7 6 5 3 from index 10: Path: 13 9 5 3 from index 6: Path: 12 8 3 from index 0: Path: 3
= newline. The output ends with a newline — print one after the last line.
Your Output
Run your code to see the output here...