get root of a binary search tree in java

Question

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 ?

Willem Van Onsem Willem Van Onsem · Accepted Answer · 2014-12-14T15:31:24

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.

get root of a binary search tree in java

2 Answers