Exercise: Random Binary Search Trees

Task

Design and implement an algorithm that constructs a Treap from a sorted array, a, of n elements. This method should run in $O(n$ ...