Binary Search Tree Traversals failed to execute when using recursion

I am new to Java programming and data structures. Nevertheless I could implement the following code after so many efforts. There I need to insert values to nodes, and print the values in each node to demonstrate all 03 types of depth first traversal techniques with the help of recursion.

PreOrder traversal
PostOrder traversal
InOrder traversal

I have developed 03 separate methods to implement above 03 traversal methods. (I have commented the particular sections in the code given at the end of the question)

But when I try to run the code I get the following Error message Click here to view And for the reference I provided the error message in text format as below.

Exception in thread "main" java.lang.NullPointerException
data -> 14
data -> 5
null
    at BSTreeDemo.BSTree.preOrderTraversal(BSTreeDemo.java:75)
    at BSTreeDemo.BSTree.preOrderTraversal(BSTreeDemo.java:75)
    at BSTreeDemo.BSTree.preOrderTraversal(BSTreeDemo.java:75)
    at BSTreeDemo.BSTree.preOrderTraversal(BSTreeDemo.java:75)
    at BSTreeDemo.BSTreeDemo.main(BSTreeDemo.java:16)

I do not understand why I am getting the above error. Because in my perspective my approach is correct.

Following is the complete code I implemented

package BSTreeDemo;

public class BSTreeDemo {

    public static void main(String[] args) {    //Main class
        BSTree t1 = new BSTree();
        t1.addNode(25);
        t1.addNode(14);
        t1.addNode(78);
        t1.addNode(45);
        t1.addNode(5);
        t1.addNode(89);
        
        System.out.println("-------------PreOrderTraversal------------");
        t1.preOrderTraversal(t1.root); 
        System.out.println("-------------PostOrderTraversal------------");
        t1.postOrderTraversal(t1.root); 
        System.out.println("-------------InOrderTraversal------------");
        t1.inOrderTraversal(t1.root); 
        
    }
    
}

class BSTNode {         // Binary Search tree node class
    int data; 
    BSTNode leftChild; 
    BSTNode rightChild; 
    
    public BSTNode(int data){ 
        this.data=data; 
    } 
    @Override 
    public String toString(){ 
        return "data -> "+data; 
    } 
}

class BSTree {
    
    BSTNode root; 
    
    public void addNode(int data) {     // method to add values to each node in binary search tree
        
        BSTNode newNode = new BSTNode(data);
        
        if(root == null){
            root=newNode;
        }
        else{
            BSTNode currentNode = root;
            while(true){
                BSTNode parentNode = currentNode;
                if(newNode.data<currentNode.data){
                    currentNode=currentNode.leftChild;
                    if(currentNode==null){
                        parentNode.leftChild = newNode;
                        return;
                    }
                }
                else{
                    currentNode = currentNode.rightChild;
                    if(currentNode ==null){
                        parentNode.rightChild = newNode;
                        return;
                    }
                }
            }
        }
    } 
    
    public void preOrderTraversal(BSTNode currentNode){ // Recursive function to print the values in Pre-Order traversal
        System.out.println(currentNode);
        preOrderTraversal(currentNode.leftChild);
        preOrderTraversal(currentNode.rightChild);
        
        
    }
    
    public void postOrderTraversal(BSTNode currentNode){ // Recursive function to print the values in Post-Order traversal
        postOrderTraversal(currentNode.leftChild);
        postOrderTraversal(currentNode.rightChild);
        System.out.println(currentNode);  
    }
    
    public void inOrderTraversal(BSTNode currentNode){   // Recursive function to print the values in In-Order traversal
        inOrderTraversal(currentNode.leftChild);
        System.out.println(currentNode);       
        inOrderTraversal(currentNode.rightChild); 
    }
}

Can somebody please look through my code and please be kind to show any stupid mistake I have made for not to run the code successfully, and the reason why I am getting above mentioned error? I am really sucked at this point.

Thanks in advance.

Answer

You’re missing base condition of your recursive traversal functions which is if (currentNode == null) return;

Example:

public void postOrderTraversal(BSTNode currentNode){ // Recursive function to print the values in Post-Order traversal
    if (currentNode == null)
        return;

    postOrderTraversal(currentNode.leftChild);
    postOrderTraversal(currentNode.rightChild);
    System.out.println(currentNode);
}

Advertisement

Answer