# Exercise: Random Binary Search Trees

Implement a treap from a sorted array.

## We'll cover the following

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

**Sample input**

The sample input will be as follows:

```
1
2
3
4
5
6
```

**Expected output**

The expected output will be as follows:

```
Tree contents:
1 2 3 4 5 6
Tree contents after removing 4:
1 2 3 5 6
```

Create a free account to access the full course.

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