CODEWITHSUNDEEP
javabinary-treebinary-search
user472221
user472221

Reputation: 3124

binary search tree

Hi I have an array list which has some numbers in it like {23,16,45,26,2,5,9} and I want to make a binary search tree with this array list which is "array" and its elements are objects that has 2 fields,1)digit2)level but here I just want to use its digit field.Also dList is a DoublyLinkedList. this is my code but it will throw an exception.please help me , thanks.

    private void method(ArrayList<Element> array) {
    DNode header = new DNode(null, null, null);
    DNode trailer = new DNode(null, header, null);
    header.next = trailer;
    DNode node = new DNode(array.get(0), header, trailer);
    dList.addLast(node);
    header = node
    for(int i = 1;i<array.size();i++){
    makeBST(node, array.get(i));
    }
}

private void makeBST(DNode node, Element e) {

    if (!e.equals(node.getElement())) {
        DNode nodeOne = new DNode(e, null, null);
        if (node.getElement().getDigit() > e.getDigit()) {
            node.prev = nodeOne;
        } else if (node.getElement().getDigit() < e.getDigit()) {
            node.next = node;
        }
    }
    if (e.getDigit() < node.getElement().getDigit()) {
        makeBST(node.prev, e);
    }
    makeBST(node.next, e);
}

Exception:

Exception in thread "main" java.lang.StackOverflowError
    at OBST.GreedyVersion.makeBST(GreedyVersion.java:43)
    at OBST.GreedyVersion.makeBST(GreedyVersion.java:54)
    at OBST.GreedyVersion.makeBST(GreedyVersion.java:54)
    at OBST.GreedyVersion.makeBST(GreedyVersion.java:54)

the first line of exception is for this line of code:

if (!e.equals(node.getElement()))

Upvotes: 0

Views: 794

Answers (4)

Michael Wiles
Michael Wiles

Reputation: 21194

I can see that you're trying, but you're a long way from the solution.

You're using recursion so you need a stopping case... which you don't have.

You should also probably have if... else if ... rather than what you have got (if ... if ...)

That line if (!e.equals(node.getElement())) { makes no sense either...

Check out the wikipedia articles on binary trees and binary search trees... will probably help.

Upvotes: 0

iirekm
iirekm

Reputation: 9446

Your code basically is:

private void makeBST(DNode node, Element e) {
    // ... (the rest of your code)
    makeBST(node.next, e);
}

It's almost equivalent to:

private void makeBST(DNode node, Element e) {
    while(true) {
        // ... (the rest of your code)
        node = node.next;
    }
}

You just made an infinite loop (but not with while, but with recursion). Because stack size is very limited, after some iterations you get StackOverflowError.

But anyway, if it's just an educational experiment it's OK. If you just need a working BST, use java.util.TreeSet or java.util.TreeMap.

Upvotes: 1

Jason S
Jason S

Reputation: 189856

You've got a StackOverflowError, which points towards an infinite (well, potentially at least) recursion error.

p.s. why not just use a TreeMap<K,V> where K is the index of your data, and V is the data value?

Upvotes: 0

Assaf
Assaf

Reputation: 1346

your recursive method "private void makeBST(DNode node, Element e)" needs some type of ending condition (a flow path which will prevent it from calling itself); as it is, it keeps calling itself recursively which is what is causing your stack overflow error.

Upvotes: 3

Related Questions