3. (6pts) Fill in the six blanks to complete the proof that a binary tree of n nodes has the depth at least lg(n +1)-1 where lg n = log2 n Allowed key strokes: Ig \g, max 1max o You must use them to express lg and max. Add an extra space at the end of each keystroke and variable - Put a pair of parentheses to avoid any ambiguity. " max (x, y) : the maximum of x, y \lg (x-y): Ig ofx-y. Don't write Vgx - y unless you mean (Ngx) -y * Each blank must be filled with the case-sensitive shortest possible expression. - Such a binary tree has n nodes connected by edges, without creating a cycle (a path starting and ending at a same node). So its example looks like: roo Sjnary Tre T 2eff to a node. The depth is the number of the edges from the root to the deepest node. In this case it's 3. we prove by induction on n E Z+ that the depth of T is at least lg(n + 1)-1. Its base case occurs when n-(a) true for 1, 2, 3,., n and prove true for_(b) . The claim is clearly true. To prove the induction step, assume Let m be the number of nodes in the left subtree of the root r. There are nodes in the right subtree of r. By induction hypothesis, the depth of T is at least--(d) Here (d) is - an expression including m, \g and max, obtained by applying the induction hypothesis directly, - but of the minimum length