10.3.2. Child and Parent Node Calculation

Try these first

1. 1.

   What is the height of a tree with 7 nodes?

   Hint

   Think about how many levels exist in a perfectly balanced tree.

2. 2.

   Where would the child nodes be for the node at index 1?

   Hint

   Use the formulas `2i + 1` and `2i + 2`.

3. 3.

   What is the time complexity for insertion in a heap?

   • O(N)
   • O(log N)
   • O(1)

   Hint

   Consider the height of the tree as it grows.

4. 4.

   In a max heap, which holds true?

   • True
   • False

   Hint

   Visualize a binary tree where the root is the greatest value.

5. 5.

   Given an initial max heap with the values [25, 20, 10, 5, 15], after inserting 30, what will the new heap look like?

   Hint

   Remember to bubble up the new value to maintain heap properties.

6. 6.

   Explain how you would convert a given unsorted array into a min heap using the bottom-up heapification method.

   Hint

   Start from the lower levels of the tree, as leaves will already be in min heap order.