0

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()))
Improve this question

4 Answers 4

Reset to default
3

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.

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

4 Comments

how can i finish its recursive call?
I think you need a "return" at the end of the first if block. Or, with the same result, you can put the recursive makeBST calls into appropiate "else if" blocks.
@user472221, TToni and iirekm have got it right. For a recursive end condition, you need to think about when the recursion needs to stop (hint: what happens when you have a tree of size 0 or size 1?) - and when that condition is hit, you need to make sure the function stops calling itself.
yes you are right now it doesn't throw this exception thanks!
1

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.

Improve this answer

1 Comment

how can i make a BST with treeSet or treeMap?would you help me?
0

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?

Improve this answer

Comments

0

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.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.