CJCoding With Joseph
15free / daySign inCreate account

Check Whether a Heap Node Has Children

Complete has_left_child and has_right_child. Each one takes the heap and an index i, and returns 1 when the node at i really has that child inside the heap, or 0 when it does not.

Reminder: a child index can point past the end of the heap. A min heap is a complete binary tree kept in an array, filled row by row, left to right, with no gaps. For index i the left child is at 2 * i + 1 and the right child is at 2 * i + 2, but that arithmetic gives an answer for any i, even when it names a slot nobody has filled. Only the first heap->size slots hold heap values, so a child exists only when its index is smaller than heap->size. A node with no children at all is called a leaf.

size = 6, so the heap uses index 0 to 5
index:   0   1   2   3   4   5
value:   3   7   4   9   8   5

            3
          /   \
         7     4
        / \   /
       9   8 5   .

index 0: children at index 1 and 2, both < 6
index 1: children at index 3 and 4, both < 6
index 2: left at index 5 < 6, right at index 6 is not < 6
the dot is index 6, one past the end: the 4 has a left child but no right child
leaves: index 3, 4 and 5 (their left children would be index 7, 9 and 11, all >= 6)

Index 2 is the interesting one: its left child is there, but its right child would be index 6, and the heap stops at index 5. Because the last row fills from the left, a node can have a left child and no right child, but never a right child without a left one. Leaves are not only in the bottom row: when the bottom row is only partly filled, nodes in the row above it can be leaves too.

Requirements: 1. has_left_child(heap, i) returns 1 when the left child of i is inside the heap (its index is less than heap->size), otherwise 0. 2. has_right_child(heap, i) does the same check for the right child of i. 3. Use the provided get_left_child_index and get_right_child_index for the index math. 4. An empty heap has no children anywhere, and in a heap of one value the root is a leaf. 5. Only compare indexes, never read heap->data, and leave the other functions as they are.

Do NOT write a main function.

Expected Output:

MinHeap: 2 5 3 8 6 4 9 10
index 0 (2): left yes, right yes
index 1 (5): left yes, right yes
index 2 (3): left yes, right yes
index 3 (8): left yes, right no
index 4 (6): left no, right no
index 5 (4): left no, right no
index 6 (9): left no, right no
index 7 (10): left no, right no
leaves: 6 4 9 10

= newline. The output ends with a newline — print one after the last line.

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