Let's assume I have array which I need to parse into binary tree

[10, 15, 8, 12, 94, 81, 5, 2, 11]:

         /  \
        8   15
       /   /  \
      5   12  94
     /   /   /
    2   11  81

or slightly modified arrays with the same elements generate the same binary tree above: [10, 8, 5, 15, 2, 12, 11, 94, 81] or [10, 15, 94, 8, 5, 2, 81, 12, 11]

The first element of the array is always root of the binary search tree. The parsing should populate the tree from array sequentially without swapping/sorting elements in the array.

Something like this:

data class Node(
      val value: Int,
      var left: Node? = null,
      var right: Node? = null

 fun Node.populateNode(currentValue: Int) {
        if(value <= currentValue) {
            if(right == null)
                right = Node(currentValue)
            else right?.populateNode(currentValue)
        } else if(left == null)
                left = Node(currentValue)
        else left?.populateNode(currentValue)

 fun IntArray.parseToBst(): Node? {
        val root = Node(first())
        for(i in 1 .. lastIndex) {
        return root


val tree = intArrayOf(10, 8, 5, 15, 2, 12, 11, 94, 81).parseToBst()

I wonder if is any more efficient algorithm (faster in terms of time complexity) to parse binary search tree from array by requirements described above?

  • $\begingroup$ Do the same thing but with an AVL tree or any other self-balancing tree: en.wikipedia.org/wiki/Self-balancing_binary_search_tree $\endgroup$
    – nir shahar
    Commented Jul 3, 2021 at 9:11
  • $\begingroup$ @nir: I think the constraint "without sorting or swapping" precludes the use of balancing algorithms such as AVL. It seems that OP wants the "natural" BST encoded in the sequence, even if it is highly unbalanced. $\endgroup$
    – rici
    Commented Jul 3, 2021 at 19:56
  • $\begingroup$ @rici its impossible to translate a sequence into a BST without sorting it first. The OP meant that you are not allowed to change the array. So doing balancing operations on an AVL tree doesn't really seem to violate that constraint. $\endgroup$
    – nir shahar
    Commented Jul 4, 2021 at 6:27
  • $\begingroup$ @nir: If you just add each element in turn from a sequence into a binary tree, you get a BST. OP's algorithm shows how to do that. There's no need to sort it first. The rotations done by AVL (etc.) are to produce a semi-balanced BST, but a BST is still a BST even if it isn't balanced. If you know the sequence is the result of a preorder traverse of a BST, then there's a linear-time algiorthm to recover the original BST (and it will be linear-time no matter how unbalanced the tree is). But that's not what OP is asking for; I don't think they want to limit the sequence. $\endgroup$
    – rici
    Commented Jul 4, 2021 at 7:27
  • $\begingroup$ @rici just inserting normally into a (non-balanced) BST will take up to $O(n^2)$ worst case. When using AVL-trees, each insert is $O(\log(n))$ amortized, hence inserting the entire tree will take $O(n\log(n))$ worst case. The speedup here comes from the balance the AVL keeps. $\endgroup$
    – nir shahar
    Commented Jul 4, 2021 at 7:58

2 Answers 2


There's a linear-time algorithm to reconstruct a binary search tree given a depth-first preorder left-to-right traverse. But it seems to me that what you're looking for is an algorithm which will work with a traverse which only satisfies the property that a parent appears before its children.

The algorithm you present is $O(N log N)$ on average, but worst case $O(N^2)$. I don't believe you can improve on the average construction time of $O(N log N)$ but I think you can improve the worst case behaviour by maintaining the list of insertion ranges in a semi-balanced binary search tree (such as a red-black or AVL tree) where each node points at the parent node for that range.


A BST traversal will output the keys in sorted order in linear time, so no comparison-based tree building algorithm can work faster than in $O(n\log n)$ time.

As said at other places, this bound can be reached by filling a balanced BST one key at a time, and this is optimal. If the balance condition is not enforced, the worst-case time can get... worse. Randomizing could ensure expected $O(n\log n)$ time, but your question does not allow this.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.