Answer Happy

(2) Question 2: Problem 37 on page 64 of Erickson). You can assume the tree is represented by a linked data structure. Each node has a pointer to its left and right child and its parent. For example, if v is a node, then v.left, v.right, v.parent point to its left child, right child, and parent respectively. If v.left = NULL, that means v does not have a left child (and similarly for v.right and v.parent. 37. For this problem, a subtree of a binary tree means any connected subgraph. A binary tree is complete if every internal node has two children, and every leaf has exactly the same depth. Describe and analyze a recursive algorithm to compute the largest complete subtree of a given binary tree. Your algorithm should return both the root and the depth of this subtree. See Figure 1.26 for an example. Figure 1.26. The largest complete subtree of this binary tree has depth 3.