Binary Search Tree in Java using arrays

Question

I'm trying to write an array implementation of Binary Search Trees in Java. To that end, I have the following two methods that are responsible for making sure all the data gets added into the array properly

private int[] testData = {50, 25, 75, 10, 15, 5, 53, 29, 79, 78, 111, 33};
private int[] tree = new int[100];
private final int ROOT = tree.length / 2; //Root is at the center of the array

public void insert(int key)
{
    if(tree[ROOT] == 0)
    {
        tree[ROOT] = key;
    }
    else
    {
        int locToInsert = findLocationToInsert(ROOT, key);
        if(locToInsert == -1)
        {
            System.out.println("Error: Tree branch full");
        }
        else
        {
            tree[locToInsert] = key;
        }
    }
}

public int findLocationToInsert(int c, int key)
{
    if(tree[c] != 0) //If current c is not empty
    {
        if(key > tree[c]) //Go right to find an empty c
        {
            findLocationToInsert(c + c/2, key);
        }
        else //Go left to find an empty c
        {
            findLocationToInsert(c - c/2, key);
        }
    }
    return c;
}

However, my recursive findLocationToInsert method always returns the root. How do I fix this implementation to return the first empty location it finds?

Also, I don't see how the math here works out. c/2 is going to produce different numbers depending on whether you go left or right. That can' be right. Look instead how a Heap is implemented. — markspace
– markspace, Commented Feb 25, 2015 at 21:43

RealSkeptic · Accepted Answer · 2015-02-25 21:47:13Z

1

Your recursive function doesn't do anything with the results of its recursive calls.

       findLocationToInsert(c + c/2, key);

As you can see, you are not assigning the returned value to anything, so it is just discarded.

So after your if or your else is executed, it simply goes to the line return c and returns the original c that it got - which is the root.

Before you decide what you want to do with the values of the recursive call, you should take care of another problem: you don't have a stop condition.

If you actually fill your tree, you are supposed to return -1 according to your other method. But there is no place in your function that returns a -1. If the tree is full it's going to get stuck in an endless loop and you'll get a stack overflow.

answered Feb 25, 2015 at 21:47

RealSkeptic

34.8k7 gold badges56 silver badges83 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Binary Search Tree in Java using arrays

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related