CODEWITHSUNDEEP
javabinary-treenodesbinary-search-tree
rawData
rawData

Reputation: 799

get root of a binary search tree in java

I have created a binary search tree in java that allow user to add nodes to the tree

This is my implementation of the binary tree in java which accept root node on creation and then automatically figure out that it should add the child into left side or right side of the tree. 

public class BinarySearchTree {

    Node root = null;
    public BinarySearchTree(Node root){
        this.root =root;
    }
    public void add(int data){
        Node newNode = new Node(data);
        if(this.root ==null){
            newNode =this.root;
        }
        if(data>this.root.data){
            addRight(root,newNode);
        }

        if(data<this.root.data){
            addLeft(root,newNode);
        }
    }

    public Node getRoot(){
       return  this.root;
    }

    private void addLeft(Node root, Node newNode) {
        if(root.leftChild == null){
            root.leftChild = newNode;
        }
        else {
            this.root = this.root.leftChild;
            add(newNode.data);
        }
    }

    private void addRight(Node root,Node newNode) {
        if (root.rightChild == null){
            root.rightChild = newNode;
        }
        else {
            this.root = this.root.rightChild;
            add(newNode.data);
        }
    }

}

But when I try to retrieve the root node with getRoot() method. it return me the child of the root rather than the actual root node that I had passed in.

this is a example of using it 

TreeHight treeHight = new TreeHight();
        Node root = new Node(100);
        BinarySearchTree unbalance = new BinarySearchTree(root);
        unbalance.add(200);
        unbalance.add(50);
        unbalance.add(250);
        unbalance.add(350);

when I try to get root node it give me 250 as the first node rather than 100.

How can I retrieve the root node of this tree ?

Upvotes: 3

Views: 12633

Answers (2)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476544

In your code you write:

 this.root = this.root.leftChild;
 add(newNode.data);

This is probably wrong behavior?

You should rewrite it to:

add(this.root.leftChild,newNode);

And then define a recursive method that looks whether the item should be stored left/right of the subroot.

Something like:

public void add(Node subroot, int data){
    if(data > subroot.data){
        addRight(subroot,data);
    }
    else if(data < subroot.data){
        addLeft(subroot,newNode);
    }
}

private void addLeft(Node subroot, int data) {
    if(subroot.leftChild == null){
        subroot.leftChild = new Node(data);
    }
    else {
        add(subroot.leftChild,data);
    }
}

private void addRight(Node subroot, int data) {
    if(subroot.rightChild == null){
        subroot.rightChild = new Node(data);
    }
    else {
        add(subroot.rightChild,data);
    }
}

And the add method is then:

public void add(int data){
    if(this.root == null){
        this.root = new Node(data);
    }
    else {
        this.add(this.root,data);
    }
}

I think an invariant of a binary tree is that the root remains the same. The same goes for addRight by the way.

Finally you also wrote:

newNode =this.root;

in your add method, this of course, doesn't make much sense.

Upvotes: 7

walid
walid

Reputation: 492

You are editing the root in this line:

this.root = this.root.rightChild;

I think you should add the new node to the right recursively like this:

    else {
        addRight(this.root.rightChild, newNode);
    }

And just as a note i think you have problem in this block "in the add method":

   if(this.root ==null){
        newNode =this.root; // it should be this.root = newNode;
    }

Upvotes: 1

Related Questions