1
$\begingroup$

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?

$\endgroup$
6
  • $\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
    Jul 3 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
    Jul 3 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
    Jul 4 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
    Jul 4 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
    Jul 4 at 7:58
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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