Binary search tree null pointer exception with traversal

Question

I am implementing a binary search tree in java, writing the methods recursively. I did the insert methods, and now I am stuck on the first traversal method, the in order one. When I call it in my test code, after adding a few elements, (tree.inorderTraversal), I get a null pointer exception at the rescursive in order method, and I don't see why. Could it be something wrong with the insert method?

public void insertInBinaryTree(E newItem)
{
    BinaryTreeNode<E> node = new BinaryTreeNode<E>(newItem);
    if (root == null) {
        root = node;
    } else {
        insert(root, newItem);  
    }
}

// Recursively insert a node containing newItem into a non-empty tree. Used
// by insertInBinaryTree
private void insert(BinaryTreeNode<E> treeNode, E newItem)
{
    if (newItem.compareTo(treeNode.getItem()) < 0) {
        if (treeNode.getLeftChild() != null) {
            insert(treeNode.getLeftChild(), newItem);
        }
        else {
            treeNode.setLeftChild(new BinaryTreeNode<E>(newItem));
        }
    }
    else {
        if (treeNode.getRightChild() != null) {
            insert(treeNode.getRightChild(), newItem);
        }
        else {
            treeNode.setRightChild(new BinaryTreeNode<E>(newItem));
        }
    }
}

// If the tree is not empty, initiates an inorder traversal. This should
// print all items in ascending order. If the tree is empty, just prints
// "Tree is empty"
public void inorderTraversal()
{
    System.out.println("\nInorder Traversal");

    if (root == null) {
        System.out.println("Tree is empty");
    } else {    
        inorder(root);
    }


}

// Recursive inorder traversal of a non-empty tree. Used by
// inorderTraversal.
private void inorder(BinaryTreeNode<E> treeNode)
{
    inorder(treeNode.getLeftChild());
    System.out.print(treeNode.getItem());
    inorder(treeNode.getRightChild());
}

score 0 · Answer 1 · answered Jul 08 '17 at 17:19

0

You are missing NULL check. It should be

private void inorder(BinaryTreeNode<E> treeNode)
{
    if(treeNode != null)
    {
    inorder(treeNode.getLeftChild());
    System.out.print(treeNode.getItem());
    inorder(treeNode.getRightChild());
    }
}

answered Jul 08 '17 at 17:19

Ravi

30,829
42
119
173

You should thank by accepting the answer :P – Ravi Jul 08 '17 at 17:45

score 0 · Accepted Answer · answered Jul 08 '17 at 17:27

In the inorder method, since its recursive method the first statement should check for null on the argument and if it is so it should return. Otherwise the recursion never ends and it runs into NPE when accessing treeNode.getLeftChild() or treeNode.getRightChild() on possible null when there is no left child node or right child node.

Binary search tree null pointer exception with traversal

2 Answers2