PLEASE SHOW ALL STEPS WHEN SOLVING THIS

Problem 2. A perfect binary tree is a tree in which every node other than the leaves has exactly two children, and the leaves are all at the same level. We are going to find the exact number of comparisons (in the worst case) for heap creation in a perfect binary tree. We will guess the formula by looking at a few small examples, and then prove it is correct by mathematical induction (a) The height of a tree is the number of levels of nodes. (A tree consisting of a single root node has height 0. A tree consist ing of a root node with some children has height 1. Etc.) (i) Assume a perfect binary tree has height h. How many nodes does it have? Justify. (b) Calulate by hand the exact number of comparisons for complete trees with heights (c) We know that the true answer should be approximately 2n. Find the differences between (d) Guess a formula for your differences as a function of n (ii Assume a perfect binary tree has n nodes. What is its height? Justify. 0, 1,2,3,4 2n and your calculated values. (e) What formula does that give you for the exact number of comparisons for heap creation as a function of n