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 ign = log2 n Allowed key strokes: lg Add an extra space at the end of each keystroke and variable lg, max max' o You must use them to express lg and max. Put a pair of parentheses to avoid any ambiguity. \max (x, y) : the maximum of x, y - Vg (x-y): Ig of x-y. Don't write \Ig x - y unless you mean (\Igx)-'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: Too lef f n:I : # nodes Subtre ro the root to a node eanode has 2 childran ren 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 EZ+ that the depth of T is at least lg(n +1) -1. Its base case occurs when n= true for 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, \Ig and \max, obtained by applying the induction hypothesis directly, but of the minimum length