Instead of creating new arrays to represent the inorder and preorder traversal of the subtrees, it is possible to save space by passing a pair of indices instead. Observe that the inorder/preorder traversal of the left and right subtrees are just contiguous segments of the inorder/preorder traversal of the whole tree. Therefore, we can represent the inorder/preorder traversal of the subtrees using a start and end index.

A variant is to determine whether a given binary tree is complete in O(n) time. What is the simplest algorithm for this problem? Hint: think about the fact that a complete tree can be stored in an array.

Notice that in the first method (insert one-by-one), in the worst case the nodes that are initially inserted at the last level might have to bubble up all the way to the top. There are `O(n/2)` nodes which may need to bubble up `O(\lg n)` levels, hence the complexity is at least `O(n \lg n)`.

On the other hand for the heapify method, the nodes bubble down. The majority of the nodes are near the bottom and the number of level they can bubble down is small, while nodes near the top have to move further there is much less of them. All in all, the maximum number of comparisons is `O(n)`

Cecilia R. Aragon and Raimund Seidel developed the Treap data structure in 1989. It is known that for a random insert order, the resulting binary tree is expected to have height `O(\lg n)`. By assigning each new node with a random priority value and rotating the nodes to satisfy the heap property on the priority value it can be shown that the resulting tree is similar to one constructed by inserting the nodes in random order.