Constructing a Binary Search Tree [algorithm puzzle]

Suppose you are given a sequence of distinct numbers $a_1, a_2, \dots, a_n$.

You can create a unique binary search tree of those numbers by inserting $a_1$, then $a_2$ etc in the order they appear.

$a_1$ becomes the root, if $a_2 \gt a_1$, then it becomes the root of the right sub-tree and so on. Note that the sequence uniquely determines the tree.

For example, if the sequence was $4,5,1,2,3$ the corresponding binary search tree would look like

Tree formed by inserting 4, then 5,1,2,3 in order.

Now suppose you wanted to write a program to create the final binary search tree corresponding to a given insertion order.

A naive solution would be to run the binary search tree insertion algorithm for each element in the sequence to get the final tree. In the worst case, this creation algorithm would be quadratic in the number of elements in the sequence: if the sequence was sorted, for e.g.

This puzzle is about doing the binary search tree construction better.

Can you give an $O(n \log n)$ worst-case time algorithm which will construct the binary search tree of the given insertion sequence of distinct numbers $a_1, a_2, \dots, a_n$? Note that the resulting tree should be the same as the one gotten by the naive algorithm.

(Assume a pointer based tree, with left and right pointers, and if needed, parent pointers)

[Solutions]