I need to implement a Binary search tree in Java (only insert and find) and then should be able to display the tree.
This is the code I've come up with so far. But I get the nullpointer exception. I am getting this because the two pointers in my node, leftChild and rightChild are set to null and don't point anywhere. But I don't know how to fix this. How do I make it so that they point to the correct nodes?

import java.util.*;

public class RBTTree
{

	RBTNode root = null; //Root node of the tree
	RBTNode currentNode = null;

//Checks to see if tree is empty. Prints out message if it is.
	void IsEmpty()
	{
		if(root == null)
			System.out.println("Tree is Empty");
	}//End of IsEmpty

	RBTNode create(int number)
	{
		RBTNode node = new RBTNode();
		node.number = number;
		node.parent = null;
		node.leftChild = null;
		node.rightChild = null;
		//System.out.println("Node.data is: " +node.data);
		return node;
	}

//Method to insert a number into the tree.
	public void insert(int number)
	{
		IsEmpty();

		root = insert (root,number);

		System.out.println("Node just inserted: " + root.number);
		System.out.println("Node's left child: " + root.leftChild);
		System.out.println("Node's right child: " + root.rightChild);
	}

	RBTNode insert(RBTNode node, int number)
	{
		if(node == null)// create a new node.
		{
			node = create(number);
		}
		else if(number < node.number)// if the number is less than the node, go to the left child.
		{
			node.leftChild = insert(node.leftChild,number);
		}
		else if(number > node.number)// if the number is greater than the node, go to the right child
		{
			node.rightChild = insert(node.rightChild,number);
		}
		else if(number == node.number) //if the number already exists in the the tree, place it in the right child.
		{
			node.rightChild = insert(node.rightChild, number);
		}

		return node;
	}// end BSTNode insert


	public void find(int number)
	{
		IsEmpty();

		currentNode = find(root, number);

		System.out.println("Search returned Node: " + currentNode.number);
		System.out.println("Node's left child: " + currentNode.leftChild);
		System.out.println("Node's right child: " + currentNode.rightChild);

	}//End of find

	RBTNode find(RBTNode currentNode, int number)
	{
		//currentNode = root; //sets the root node to the current node for searching purposes

		while(currentNode.number != number && currentNode != null)
		{
			if(number < currentNode.number) //if number we are searching for is less than the node search left sub tree
			{
				currentNode = currentNode.leftChild;
			}
			else if(number > currentNode.number)//if number we are searching for is greater than the node search right sub tree
			{
				currentNode = currentNode.rightChild;
			}
			else	//if number we are searching for is equal to the node search right sub tree
			{
				currentNode = currentNode.rightChild;
			}
		}

		return currentNode;

	}//End of RBTNode find


//Print all items.
    public void printTree( )
    {
        display(root);
    }

	private void display(RBTNode currentNode)
	{
		if(root == null)
			System.out.println("Empty Tree. Nothing to display");

        else
        {
            display(currentNode.leftChild);
            System.out.println(currentNode.number);
            display(currentNode.rightChild);
        }


	}//End of display

	public static void main(String[] args)
	{
		RBTTree RBT = new RBTTree();

		Scanner console = new Scanner(System.in);

		System.out.println("How many numbers would you like to enter into the Red Black Tree?");
		int k = console.nextInt();

		int inputarray[] = new int[k];

		for(int i=0; i< k; i++)
		{

			System.out.println("Please enter the " + (i+1)+ " number: ");
			inputarray[i]= console.nextInt();
		}

		for(int i=0; i<k; i++)
		{
			RBT.insert(inputarray[i]);
		}
	}


}//end of class RBTTree

My RBTNode is here

class RBTNode
{
	int number;
	RBTNode parent;
	RBTNode leftChild;
	RBTNode rightChild;

}
import java.util.*;

public class RBTTree
{

	public RBTNode root = null; //Root node of the tree
	RBTNode currentNode = root;

//Checks to see if tree is empty. Prints out message if it is.
	public boolean IsEmpty()
	{
		if(root == null)
			return true;
		return false;
	}//End of IsEmpty

	RBTNode create(int number)
	{
		RBTNode node = new RBTNode();
		node.number = number;
		node.parent = null;
		node.leftChild = null;
		node.rightChild = null;
		//System.out.println("Node.data is: " +node.data);
		return node;
	}

//Method to insert a number into the tree.
	public void insert(int number)
	{	
		
		
		currentNode = add (root,number);
		if(IsEmpty() == true && currentNode != null)
		root = currentNode;
		currentNode = root;
	}

	RBTNode add(RBTNode node, int number)
	{
		if(node == null)// create a new node.
		{
			node = create(number);
			return node;
			
		}
		else if(number < node.number)// if the number is less than the node, go to the left child.
		{
			if(node.leftChild != null)
			add(node.leftChild,number);
			else
			node.leftChild = create(number);
			
		}
		else if(number >= node.number)// if the number is greater than the node, go to the right child
		{
			if(node.rightChild != null)
			 add(node.rightChild,number);
			else
			node.rightChild = create(number);
		
		}
		
		 return null;
		
	}// end BSTNode insert


	public void find(int number)
	{
		IsEmpty();

		currentNode = find(root, number);

		System.out.println("Search returned Node: " + currentNode.number);
		System.out.println("Node's left child: " + currentNode.leftChild);
		System.out.println("Node's right child: " + currentNode.rightChild);

	}//End of find

	RBTNode find(RBTNode currentNode, int number)
	{
		//currentNode = root; //sets the root node to the current node for searching purposes

		while(currentNode.number != number && currentNode != null)
		{
			if(number < currentNode.number) //if number we are searching for is less than the node search left sub tree
			{
				currentNode = currentNode.leftChild;
			}
			else if(number > currentNode.number)//if number we are searching for is greater than the node search right sub tree
			{
				currentNode = currentNode.rightChild;
			}
			else	//if number we are searching for is equal to the node search right sub tree
			{
				currentNode = currentNode.rightChild;
			}
		}

		return currentNode;

	}//End of RBTNode find

    public RBTNode getRoot()
    {return root;}

	private void display(RBTNode input)
	{
		
		if(input == null)
		{
		return;
		}
		
		display(input.leftChild);
		System.out.println(input.number);
		display(input.rightChild);
		

	}//End of display

	public static void main(String[] args)
	{
		RBTTree RBT = new RBTTree();

		Scanner console = new Scanner(System.in);

		System.out.println("How many numbers would you like to enter into the Red Black Tree?");
		int k = console.nextInt();

		int inputarray[] = new int[k];

		for(int i=0; i< k; i++)
		{

			System.out.println("Please enter the " + (i+1)+ " number: ");
			inputarray[i]= console.nextInt();
		}

		System.out.println("\n\n****Display Start****");
		for(int i=0; i<k; i++)
		{
			RBT.insert(inputarray[i]);
		}
		RBT.display(RBT.getRoot());
	}


}//end of class RBTTree

That's the way I've always implemented it and it works fine for me. Obviously format it the way you want to. Right now it's displaying with an In-Order traversal.


Example run of the program:

How many numbers would you like to enter into the Red Black Tre
10
Please enter the 1 number:
7
Please enter the 2 number:
10
Please enter the 3 number:
2
Please enter the 4 number:
14
Please enter the 5 number:
3
Please enter the 6 number:
1
Please enter the 7 number:
2
Please enter the 8 number:
20
Please enter the 9 number:
14
Please enter the 10 number:
9


****Display Start****
1
2
2
3
7
9
10
14
14
20
Press any key to continue...

Note: There are probably leaner ways of coding it, but I went with that implementation for ease of traceability and understanding.


Okay, in truth I forgot what my own display method did and used that implementation because I was trying to work around false logic errors >.> <.<

:p

Thanks for your help, but I managed to figure out what was wrong.
What I am now getting stuck at is finding a node in the tree. My find method doesn't do what I want it to do. Basically, I want my find method to find the node I pass it, display the node's left and right children and print out an error if it cant find the node.
Can someone suggest what I should add/ change in my find method.

/*--------------------------------------------------
Binary Tree Code
---------------------------------------------------*/
import java.util.*;

public class RBTTree
{

	protected RBTNode root = null; //Root node of the tree
	protected RBTNode currentNode = null;

//Checks to see if tree is empty. Prints out message if it is.
	void IsEmpty()
	{
		if(root == null)
			System.out.println("Tree is Empty");
	}//End of IsEmpty

	RBTNode create(int number)
	{
		RBTNode node = new RBTNode();
		node.number = number;
		node.leftChild = null;
		node.rightChild = null;
		return node;
	}

//Method to insert a number into the tree.
	public void insert(int number)
	{
		IsEmpty();

		root = insert (root,number);

		System.out.println("Node just inserted: " + root.number);
		System.out.println("Node's left child: " + root.leftChild);
		System.out.println("Node's right child: " + root.rightChild);
	}

	RBTNode insert(RBTNode node, int number)
	{
		if(node == null)// create a new node.
		{
			node = create(number);
		}
		else if(number < node.number)// if the number is less than the node, go to the left child.
		{
			node.leftChild = insert(node.leftChild,number);
		}
		else if(number > node.number)// if the number is greater than the node, go to the right child
		{
			node.rightChild = insert(node.rightChild,number);
		}
		else if(number == node.number) //if the number already exists in the the tree, place it in the right child.
		{
			node.rightChild = insert(node.rightChild, number);
		}

		return node;
	}// end BSTNode insert


	public void find(int number)
	{
		IsEmpty();

		currentNode = find(root, number);

		if (currentNode == null)
		{
			System.out.println("The number you are searching for does not exist in this tree");
		}
		else
		{
			System.out.println("Search returned Node: " + currentNode.number);
			System.out.println("Node's left child: " + currentNode.leftChild);
			System.out.println("Node's right child: " + currentNode.rightChild);
		}

	}//End of find

	RBTNode find(RBTNode currentNode, int number)
	{
		//currentNode = root; //sets the root node to the current node for searching purposes

		while(currentNode.number != number && currentNode != null)
		{
			if(number < currentNode.number) //if number we are searching for is less than the node search left sub tree
			{
				currentNode = currentNode.leftChild;
			}
			else//if number we are searching for is greater than or equal to the node search right sub tree
			{
				currentNode = currentNode.rightChild;
			}
		}

		return currentNode;

	}//End of RBTNode find


//Print all items.
    public void printTree( )
    {
        IsEmpty();
        display(root);
    }
//Displays tree via in-order traversal. i.e. displays the left child then the root and then the right child
	private void display(RBTNode currentNode)
	{
		if(currentNode == null)
			System.out.println(" ");

        else
        {
            display(currentNode.leftChild);
            System.out.println(currentNode.number);
            display(currentNode.rightChild);
        }


	}//End of display

	public static void main(String[] args)
	{
		RBTTree RBT = new RBTTree();


		Scanner console = new Scanner(System.in);

		System.out.println("How many numbers would you like to enter into the Red Black Tree?");
		int k = console.nextInt();
		int input;

		int inputarray[] = new int[k];

		for(int i=0; i< k; i++)
		{

			System.out.println("Please enter the " + (i+1)+ " number: ");
			inputarray[i]= console.nextInt();
		}

		for(int i=0; i<k; i++)
		{
			RBT.insert(inputarray[i]);
		}

		RBT.printTree();

		do
		{
			System.out.println("Please enter the number you want to search for");
			int f = console.nextInt();

			RBT.find(f);

			System.out.println("Would you like to search for another number? (enter: 0= Yes/1 = No)");
			input = console.nextInt();

		}while(input == 0);


	}


}//end of class RBTTree

Here's a find method that does what you want it to and works with the code I have:

public void find(int number)
	{
		IsEmpty();

		currentNode = find(root, number);

		if (currentNode == null)
		{
			System.out.println("The number you are searching for does not exist in this tree");
		}
		else
		{
			System.out.println("Search returned Node: " + currentNode.number);
			System.out.println("Node's left child: " + currentNode.leftChild);
			System.out.println("Node's right child: " + currentNode.rightChild);
		}

	}//End of find

	RBTNode find(RBTNode tempNode, int number)
	{
			if(tempNode.number == number)
				return tempNode;
			else if(tempNode.number < number && tempNode.rightChild !=null)
				return find(tempNode.rightChild, number);
			else if(tempNode.number > number && tempNode.leftChild != null)
				return find(tempNode.leftChild, number);
			else
			return null;
	}//End of RBTNode find

Enjoy!

This article has been dead for over six months. Start a new discussion instead.