Binary Tree in Java

Question

I am trying to code up my own binary tree. Though I could find many examples for a binary search tree, I decided to write this myself.

So far, I've come upto this:

public class bTree {
bnode root=null;

void add(int val){
    bnode newnode= new bnode(val);
    bnode curr = this.root;
    bnode parent = null;

    if(this.root == null){
        this.root = newnode;
        System.out.println("Inserted at root \t"+newnode.value);
    }
    else{
            while( curr != null){
            System.out.println("Current Left and Right\t"+curr.left+"\t"+curr.right);

            if(curr.left == null){
                curr =  curr.left;
                curr = newnode;
                System.out.println("Inserted Left\t" +newnode.value);
                return;
            }
            if(curr.right ==  null){
                curr =  curr.right;
                curr = newnode;
                System.out.println("Inserted Right\t" +newnode.value);
                return;
            }
        }
    }
}

When I try to add the values to the binary tree, only the root is able to add the values. I am slowly trying to write the rest of the code where it finds the left child to be full and backtracks and all the cases. My question is why is it not even adding the next value to the left most child (in the second call to it). I'd really appreciate it if you don't give me the code, I want to learn.

doobop · Accepted Answer · 2013-09-19 05:00:48Z

3

In your statements here:

        if(curr.left == null){
            curr =  curr.left;
            curr = newnode;
            ...
        }

When you make the assignment "curr = curr.left", "curr" gets assigned null and is no longer referencing anything in the tree. So that the tree will reference it, you'll need assign the left link of "curr" to the new node

        if(curr.left == null){
            curr.left = newnode;
            ...
        }

Here's a picture showing the difference between the two: enter image description here

edited Sep 19, 2013 at 5:00

answered Sep 19, 2013 at 4:11

doobop

4,5202 gold badges33 silver badges40 bronze badges

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

Comments

johnchen902 · Accepted Answer · 2013-09-19 03:37:24Z

2

Why is it not even adding the next value to the left most child in the second call to it?

Because this do not assign curr.left to newnode:

curr = curr.left;
curr = newnode;

Fix:

curr = curr.left = newnode;

Note that there are still other bugs in your code. You'll find them out with more calls.

answered Sep 19, 2013 at 3:37

johnchen902

9,6191 gold badge29 silver badges70 bronze badges

Comments

radai · Accepted Answer · 2013-09-19 03:32:13Z

1

because when you enter you else {} curr is always != null (because curr=root and root!=null), so the loop never executes

answered Sep 19, 2013 at 3:32

radai

24.3k10 gold badges76 silver badges118 bronze badges

2 Comments

P R Over a year ago

Alright. but I don't want it to run into an infi loop. So how else could I stop it?

radai Over a year ago

the easiest solution is to use recursion instead. if you look around at almost any other tree impl you'll see recursion

Collectives™ on Stack Overflow

Binary Tree in Java

3 Answers 3

Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related