10.1.1. Height of the Tree and Complexity

Try these first

1. 1.

   Define tree height. How does it impact complexity?

   Hint

   Think about how long paths might require more steps.

2. 2.

   What is a max heap?

   Hint

   Consider who has the highest value in this structure.

3. 3.

   Where is the maximum value located in a max heap?

   • Leaf
   • Middle
   • Root

   Hint

   Recall what makes a max heap different from other trees.

4. 4.

   True or False: The height of a tree influences the time complexity of its operations.

   • True
   • False

   Hint

   Consider the path length when performing operations.

5. 5.

   Given a max heap, how would you determine its height? Provide a theoretical basis for your approach.

   Hint

   Consider how each level doubles the number of nodes added.

6. 6.

   Implement a function that constructs a min heap from a list of unsorted values. Outline your approach including time complexity.

   Hint

   What happens to leaf nodes in this process?