CJCoding With Joseph
15free / daySign inCreate account

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 stop

Starting 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.

Hints4 available
Topics:
Data Structures & AlgorithmsHeaps
1
Tab to indent (Esc then Tab to move on) · Ctrl+Enter to run · Shift+Alt+F to format · Ctrl+Space to expand shortcuts (p, fori)

Your Output

Run your code to see the output here...

Test Cases

Run your code to see test case results.