Let T be an arbitrary binary search tree on n keys. Arbitrary means that 7T is not necessarily random, so T could have height n. Consider the following process. Starting at the root of T. Flip a fair coin. If it is heads, then follow the right pointer to go down the right subtree of your current node. If it is tails, follow the left pointer to go down the left subtree of your current node. Stop when you reach a node where the result of the coin flip leads you down a null pointer. For example, if your coin flip is heads and you are at a node i in the tree that does not have a right child, then stop. This happens if i is the maximum element in the tree. (a) What is the expected length of the path that you follow from the root? (b) Let L be the length of this path. Show that there is a positive constant c such that P(L 2 clog(n)) tends to zero as n tends to infinity. Let T be an arbitrary binary search tree on n keys. Arbitrary means that 7T is not necessarily random, so T could have height n. Consider the following process. Starting at the root of T. Flip a fair coin. If it is heads, then follow the right pointer to go down the right subtree of your current node. If it is tails, follow the left pointer to go down the left subtree of your current node. Stop when you reach a node where the result of the coin flip leads you down a null pointer. For example, if your coin flip is heads and you are at a node i in the tree that does not have a right child, then stop. This happens if i is the maximum element in the tree. (a) What is the expected length of the path that you follow from the root? (b) Let L be the length of this path. Show that there is a positive constant c such that P(L 2 clog(n)) tends to zero as n tends to infinity