CODEWITHSUNDEEP
javaarraysbinary-search-tree
whowho1
whowho1

Reputation: 9

Fastest way to iterate over a Binary Search Tree (BST) stored as unordered array?

I have a BST which is stored as an array.

For example, the tree may look as follows

        4
     /    \
    2      6
   / \   /  \
  1   3  5  7

As an array, this tree would be stored as [4, 2, 6, 1, 3, 5, 7, null, etc.]

I need to implement a method to find the index of a value in O(log(n)) time. Problem is, this array is unsorted which means that I cannot implement binary search.

What would a solution look like?

I have iterated over all elements already and found a way to find the index, but it is O(n) which isn't what is required.

public class Item<A extends Comparable<? super A>>
{
protected A[] items;

public Item
    {
      //Code to construct array of size 10. 
    }

public int index(A value)
{
for (int i=0; i < items.length; i++) {
 //Method to iterate through array element by element. Time complexity of O(n).
}
}

}

That is sample code.

Thank you.

Upvotes: 0

Views: 505

Answers (2)

Sebastian Kaczmarek
Sebastian Kaczmarek

Reputation: 8515

In this implementation if a parent is on index i, its children are on 2*i + 1 (left) and 2*i + 2 (right) indexes. If it's a BST, then you always have lower values on the left, and higher on the right. That way, you can implement an algorithm which looks first at the root, if an element is lower, look in the left sub-tree, otherwise look in the right subtree. So for example:

       6
     /   \
    2     8
   / \   /  \
  1   3 7    9

the array representation would look like this:

[ 6, 2, 8, 1, 3, 7, 9 ]

and searching algorithm would look like this

int findIndex(int value, int[] bst) {
    int currentRootIndex = 0;
    while (currentRootIndex < bst.length) {
        if (value == bst[currentRootIndex]) return currentRootIndex;

        if (value < bst[currentRootIndex]) currentRootIndex = 2 * currentRootIndex + 1;
        else currentRootIndex = 2 * currentRootIndex + 2;
    }

    return currentRootIndex > bst.length ? -1 : currentRootIndex;
}

This method returns an index of searched value if the value is found. -1 otherwise.

Live demo here

Upvotes: 1

Maurice Perry
Maurice Perry

Reputation: 9651

It sounds like the element left and right link of an element at index i would be 2*i+1 and 2*(i+1). You can use the same algorithm as for a regular BST:

public int index(A value)
{
    for (int i=0; i < items.length; ) {
        if (items[i] == null) {
            return -1;
        }
        int r = value.compareTo(items[i]);
        if (r < 0) {
            i = 2*i+1;
        } else if (r > 0) {
            i = 2*(i+1);
        } else {
            return i;
        }
    }
    return -1;
}

Upvotes: 1

Related Questions