of height two similarlythe left subtree of node is perfect binary tree of height twoand the right subtree is complete binary tree of height two notes figure complete binary tree does there exist an complete binary with exactly nodes for every integer > the following theorem addresses this question indirectly by defining the relationship between the height of complete tree and the number of nodes it contains task discuss how complete and perfect trees are closely related theorem- complete binary tree of height > contains at least and at most + nodes extbfproof firstyou prove the lower bound by induction let mh be the minimum number of nodes in complete binary tree of height to prove the lower bound you must show that mh base case there is exactly one node in tree of height zero thereforem inductive hypothesis assume that mh for kfor some > consider the complete binary tree of height + which has the smallest number of nodes its left subtree is complete tree of height having the smallest number of nodes and its right subtree is perfect tree of height - from the inductive hypothesisthere are nodes in the left subtree and there are exactly ( - )+ nodes in the perfect right subtree thusmk ( - )+ + thereforeby induction mh for all > which proves the lower bound nexti prove the upper bound by induction let mh be the maximum number of nodes in complete binary tree of height to prove the upper bound must show that mh + base case there is exactly one node in tree of height zero thereforem inductive hypothesis assume that mh + for kfor some > consider the complete binary tree of height + which has the largest number of nodes its left subtree is perfect tree of height and its right subtree is complete tree of height having the largest number of nodes lovely professional university