Problem 5 - Algorithms

1.

Find a relation between the internal path length (the sum of path lengths between each internal node and the root) and the external path length (the sum of path lengths betweem each external node and the root) of a binary tree with $n$ internal nodes.

2.

Find the average number of comparisons in a successful search and in a unsuccessful search when search of a random element is performed in a binary search tree constructed from scratch by inserting a random sequence of $n$ elements.

See [SED00] for a detailed answer.