(a) The left spine of a binary tree is a path starting at the root and following only left-child pointers down to a leaf. What is the expected number of nodes in the left spine of an n-node treap?
(b) What is the expected number of leaves in an n-node treap? [Hint: What is the probability that in an n-node treap, the node with kth smallest search key is a leaf?]
(c) Prove that the expected number of proper descendants of any node in a treap is exactly equal to the expected depth of that node.