6. [A simple proof 10 points]. A perfect binary tree of height h is defined recursively as follows: an empty tree is a perfect binary tree of height -1. a non-empty tree consisting of a root r, and left and right subtrees Ti and TR, is a perfect binary tree of height h if and only if TL and TR are perfect binary trees of height h - (a) (2 points) Draw the perfect binary trees of height 0, , 2, and 3 on the lines blow. b) (3 points) Give an expression for the total number of nodes in a perfect binary tree of height h (c) (5 points) Prove that your answer to part (b) is correct by induction: Consider an arbitrary perfect binary tree of height h If h1 then the expression in part (b) gives: which is the number of nodes in a tree of height 1 otherwise, if h > -1 then we denote our tree by a root r together with subtrees TL and TR. By an inductive hypothesis that says: we have nodes in TL and nodes in TR nodes, which was what we wanted to for a total of prove