a) Given two binary trees T1 and T2, each including n distinct keys, describe an efficient algorithm that detects whether the two trees include the same keys. The algorithm returns `yes' if any key in T1 is also present in T2 and vice versa, and returns `no' otherwise. Your algorithm should run in O(n). You need to describe your algorithm in a few English sentences and provide (a short) evidence that it runs in O(n). b) We define foo trees as follows. A foo tree is a binary search tree where for every node, the heights of the left and right subtree differ by at most 10. Prove that a foo tree with n nodes has height O(log n). c) Describe an efficient algorithm for computing the height of a given AVL tree. Your algorithm should run in time O(log n) on an AVL tree of size n. In the pseudocode, use the following terminology: T.left, T.right, and T.parent indicate the left child, right child, and parent of a node T and T.balance indicates its balance factor (-1, 0, or 1). For example if T is the root we have T.parent=nil and if T is a leaf we have T.left and T.right equal to nil. The input is the root of the AVL tree.