Binary Tree using an array

Question

I am trying to insert keys from the first array and sort them into a binary tree in the second array. I know there is a problem with my insert method but I can't figure it out. Any help would be greatly appreciated

import java.util.Arrays;

public class BSTreeArray {
static int startValues[]={50, 25, 75, 10, 15, 5, 53, 29, 79, 78, 111, 33};
int [] aTree;
public BSTreeArray(){
    for(int i=0; i<startValues.length;i++){
        insert(startValues[i]);
    }
    System.out.println("Pre-Order:");
    preOrder(aTree[0], "");
}


public void insert(int key){
    aTree=new int [100];

    if(aTree[0]==0){
        aTree[0]=key;
    }

    boolean add = false;
    int curIdx=0;

    while(!add){
        if(key<aTree[curIdx]){
            //go left
            if (aTree[curIdx*2+1]==0){
                aTree[curIdx*2+1]=key;
                add = true;
            }else{
                curIdx=curIdx*2+1;
            }
        }else{
            //go right
            if(aTree[curIdx*2+2]==0){
                aTree[curIdx*2+2]= key;
                add=true;
            }else{
                curIdx=curIdx*2+2;
            }
        }
    }
}

public void preOrder(int idx, String i){
    if(idx>aTree.length){
        return;
    }else{
        System.out.println(i+aTree[idx]);
        preOrder(((2*idx)+1), i+".");
        preOrder(((2*idx)+2), i+".");

    }
}

public static void main (String []args){
    BSTreeArray a=new BSTreeArray();
}
 }

Current output:

Pre-Order:
0
.0
.0

Desired output:

50

....25

........10

............5

............15

........29

............33

....75

........53

........79

............78

............111

What's the problem? Is the output wrong? Does it not compile? Is there an exception? — Radiodef
– Radiodef, Commented Feb 25, 2014 at 20:03
@Radiodef the insert method isn't working. When the array is printed out the data is completely wrong — user3277779
– user3277779, Commented Feb 25, 2014 at 20:05
Post the actual output and also what the output should be if it worked correctly. — Radiodef
– Radiodef, Commented Feb 25, 2014 at 20:07

Radiodef · Accepted Answer · 2014-02-25 20:34:50Z

One thing I see almost immediately is the first insert will get added to the array twice.

if(aTree[0]==0){
    aTree[0]=key;
}

boolean add = false;
int curIdx=0;

while(!add){ // add is false so the loop is entered
    if(key<aTree[curIdx]){ // aTree[curIdx] == key so false

    }else{
        if(aTree[curIdx*2+2]==0){ // true because arrays are initialized
                                  // with all elements 0

            aTree[curIdx*2+2]= key; // assign key a second time
            add=true;
        }
    }
}

This might then taint all the rest of the inserts since they will get skipped ahead one node if they were to the right of the first node.

It seems like you should do this:

if(aTree[0]==0){
    aTree[0]=key;

    return; // <-
}

(Or put the rest of the method in an else block I guess.)

I compiled it and ran it myself and noticed some other simple mistakes.

You're creating a new array on every call to insert:

public void insert(int key){
    aTree=new int [100];

So you can just move new int[100] to the declaration of aTree:

public class BSTreeArray {
    int [] aTree = new int[100]; // <-

You're calling preOrder with aTree[0] instead of 0:

preOrder(aTree[0], "");

Should be:

preOrder(0, "");

Inside preOrder, you have idx>aTree.length:

if(idx>aTree.length){

This'll generate an out of bounds exception since array indexes are 0...length - 1 so it should be >=:

if(idx>=aTree.length){

Last of all, since you're using 0 to indicate an empty node you might as well check for that in preOrder:

if(aTree[idx] != 0)
    System.out.println(i+aTree[idx]);

After that the output is:

Pre-Order:
50
.25
..10
...5
...15
..29
...33
.75
..53
..79
...78
...111

As a suggestion, you might want to make your array be an Integer[] instead of an int[]. This means your int values will be boxed but it would let you use null to indicate an empty node instead of 0. Another way would be to use a long[] and have the empty value be some value int can't store like 1L << 63L (which is Long.MIN_VALUE).

No problem. Good job so far. These are just basic mistakes you can learn from. The complicated parts are the insert loop and the recursion and both of those work. As another suggestion, you could move the stuff you have in the BSTreeArray constructor to inside main. Then you have an encapsulated object and the tester stuff is outside it.

Collectives™ on Stack Overflow

Binary Tree using an array

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related