2. Write a recursive algorithm which computes the number of nodes in a general tree. 3. Show a tree achieving the worst-case running time for algorithm depth. 4. Let T be a tree whose nodes store strings. Give an efficient algorithm that computes and prints, for every node v of T, the string stored at v and the height of the subtree rooted at v. Hin Consider 'decorating' the tree, and add a height field to each node (initialized to 0) Hint 2: In some sense, depth and height are done in opposite order; depth is calculated as recursion is called (on the way down), and height is calculated as recursion returns (on the way up). 5. Let T be an ordered tree with more than one node. Is it possible that the preorder traversal of T visits the nodes in the same order as the postorder traversal of T? If so, give an example; otherwise, argue why this cannot occur. Likewise, is it possible that the preorder traversal of T visits the nodes in the reverse order of the postorder traversal of T? If so, give an example; otherwise, argue why this cannot occur. 6. For a tree T, let ni denote the number of its internal nodes, and let ne denote the number of its external nodes. Show that if every internal node in Thas exactly 3 children, then ng 2n +1. (Hint: use induction)