# More efficient way to parse array into binary search tree

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

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

10
/  \
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) {
root.populateNode(this[i])
}
return root
}


Usage:

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?

• Do the same thing but with an AVL tree or any other self-balancing tree: en.wikipedia.org/wiki/Self-balancing_binary_search_tree Commented Jul 3, 2021 at 9:11
• @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.
– rici
Commented Jul 3, 2021 at 19:56
• @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. Commented Jul 4, 2021 at 6:27
• @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.
– rici
Commented Jul 4, 2021 at 7:27
• @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. Commented Jul 4, 2021 at 7:58

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.