# Solution: Random Binary Search Trees

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

## We'll cover the following

## Task

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)$ 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.

## Solution

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