How to fix an StackOverflow Error of a Binary Tree implementation?

Question

This is an example of a Binary Tree implementation here. This code works ok. But can I create the root as single one-time node in add method.

Instead of

public void add(int value) {
 root = addRecursive(root, value);
}

i do

public void add(int value) {
 if (root == null) {
  root= new Node(value);  
  }
// then i add left- and right-leafs recursively
if (value < root.value) {
   root.left = addRecursive(root, value);        
} else if (value > root.value) {
  root.right= addRecursive(root, value); 
 }
}

And if I add 3 or less nodes - that's all right

bt.add(2);
bt.add(1);
bt.add(3);

but if I add more then 3 nodes I get StackOverflow Error because of recursive function

private Node addRecursive(Node current, int value) {      
 if (current == null) {     
  return new Node(value);
  }    
 if (value < current.value) {
  current.left = addRecursive(current.left, value);     
  } else if (value > current.value) {
    current.right = addRecursive(current.right, value);      
  }  
  return current;
}

Related: [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) — Bernhard Barker, Jun 20 '19 at 10:09

second · Answer 1 · 2019-06-20T11:25:23.837

Edit2: (reattached the original answer)

You`re problem is with this part in your add method.

if (value < root.value) {
   root.left = addRecursive(root, value);        
} else if (value > root.value) {
  root.right= addRecursive(root, value); 
 }

When calling addRecursive you should pass root.left / right instead of root itself, otherwise you end up with root.left / right == root .

Edit: As I originally wrote the problem is with the addRecursive method in your add method. But while thinking about it I somehow got confused.

Finally I understand the problem, so I added here the detailed explanation:

After the root elment has been created with the following root (value = 2, left = null, right = null)

you call the add method again with the value of 1, which causes the call

root.left = addRecursive(root, 1);

this leads to ... (note that current = root.left)

root.left = addRecursive(root.left, 1);

which the finally creates the node:

return new Node(1)

lets call it node1 (value = 1, left = null, right = null)

so you have

(in your addRescursive method)

root.left = node1

and now comes the error: you return root, which lets to

(in your add method)

root.left = root.

So replacing the call with addRecursive(root.left, value) instead of addRecursive(root, value) solves that issue.

Same issue with root.right.

Anyway that returning and assigning of already added nodes is what got me confused in the first place, so I would still suggest to seperate the recursion from the adding.

That's a good answer. So basically it gets into an infinit loop because root.left or root.right becomes actually root. For Example if you print the value of (root.right.right.right.right.right) it is still root and the program will never stop because of that — dj_frunza, Jun 20 '19 at 11:14

score 2 · Answer 2 · answered Jun 20 '19 at 10:39

2

Must be

addRecursive(root.left, value)
addRecursive(root.right, value)

i.e. not root

answered Jun 20 '19 at 10:39

Alexander Pavlov

2,264
18
25

How to fix an StackOverflow Error of a Binary Tree implementation?

2 Answers2