CODEWITHSUNDEEP
javadata-structuresbinary-tree
SNDP
SNDP

Reputation: 3

Anomaly with linking objects in Java binary tree implementation

I have implemented a simple binary tree program, but there is a problem I encounter while traversing the tree, only root element is accessed. I suspect the nodes aren't linked. I tried my best to figure out the problem but didn't find anything wrong with my code.

I tried printing the data from the insertion function, right before exiting the function, which did print the data correctly. 

public class BinaryTree {

    Node root;

    public void addNode(int data){

        Node newNode = new Node(data);

        if(root == null){
            root = newNode;
        }
        else{
            Node currentNode = root;
            while(true){
                if(data <= currentNode.data){
                    currentNode = currentNode.leftChild;
                    if(currentNode == null){
                        currentNode = newNode;
                        return;
                    }
                } 
                else{
                    currentNode = currentNode.rightChild;
                    if(currentNode == null){
                        currentNode = newNode;
                        return;
                    }
                }
            }

        }
    }

    public void inorderTraversal(Node currentNode){

        if(currentNode != null){

            inorderTraversal(currentNode.leftChild);

            System.out.print(currentNode.data + " ");

            inorderTraversal(currentNode.rightChild);

        }
    }

}

Upvotes: 0

Views: 72

Answers (2)

Pankaj Singhal
Pankaj Singhal

Reputation: 16053

You are not assigning the element to the left or right child. You are just assigning it to the local variable currentNode - which is not linked to the tree.

Follow the below code to put inside the while loop & it should work for you.

            if(data <= currentNode.data){
                if(currentNode.leftChild == null){
                    currentNode.leftChild = newNode;
                    return;
                }
                else {
                     currentNode = currentNode.leftChild;
                }
            } 
            else{
                if(currentNode.rightChild == null){
                    currentNode.rightChild = newNode;
                    return;
                }
                else {
                     currentNode = currentNode.rightChild;
                }
            }

Upvotes: 0

Tim Biegeleisen
Tim Biegeleisen

Reputation: 521093

In fact you are not adding the new node correctly to the tree during the recursive step. The logic you should be using is when you a reach a node whose left or right pointer be null, and the new node belongs in that direction, you should add the new node either to the left or right. Otherwise, keep traversing until you reach such node.

while(true) {
    if (data <= currentNode.data) {
        if (currentNode.leftChild == null) {
            currentNode.leftChild = newNode;
            return;
        }
        else {
            currentNode = currentNode.leftChild;
        }
    else {
        if (currentNode.rightChild == null) {
            currentNode.rightChild = newNode;
            return;
        }
        else {
            currentNode = currentNode.rightChild;
        }
    }
}

Keep in mind that the above simple algorithm for adding new nodes is not guaranteed to necessarily result in a balanced binary tree. To ensure that, you would have to add more logic which handle rebalancing.

Upvotes: 1

Related Questions