Solution: Random Binary Search Trees

Review the solution that implements a treap from a sorted array.

We'll cover the following


Here is the code that implements an algorithm that constructs a Treap from a sorted array, a, of n elements. This method runs in O(n)O(n) worst-case time and should construct a Treap that is indistinguishable from one in which the elements of a were added one at a time using the add(x) method.


This code widget shows the implementation of the addAll() and the addAllRecursive() methods that construct a Treap from a sorted array a of n elements.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy