Exercise: Random Binary Search Trees

Solve a task implementing 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)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