# 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 Jul 3 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
Jul 3 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. Jul 4 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
Jul 4 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. Jul 4 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.