Hey guys, trying to create a binary search tree (BST) and I dont know why but the program is not reading my insert method? When I am testing it, it shows that I did insert the number, yet when I do a check to see if the tree is empty the program says that it is empty.

Any ideas why?

//Node Class

import java.lang.*;

public class Node {
	private Node left;
	private int number;
	private Node right;
	
  	public Node() {
		left = null;
		number = 0;
		right = null;
  	}
	
	public Node(int x) {
		left = null;
		number = x;
		right = null;
	}

	public int getNumber() {
		return number;
	}

	public Node getLeft() {
		return left;
	}
	 
	public Node getRight() {
	 	return right;
	}
	
	public void setNum(int x){
		number = x;
	}

	public void setLeft(Node leftNode) {
		left = leftNode;
	}

	public void setRight(Node rightNode) {
	 	right = rightNode;
	}

}

//Binary Search Tree class

public class BST{
	private Node root;
	
	public BST(){
		root = null;
	}
	
   /*
   Checks to see if the tree is empty
   @return - true for empty
   */
	public boolean isEmpty(){
			return root == null;
	}
	
	public void inOrder(){
		inOrderHelper(root);
		System.out.println("xx" + root.getNumber());
	}
	
	private void inOrderHelper(Node t){
		if(t != null){
			
		System.out.print("TESTING");
		inOrderHelper(t.getLeft());
		System.out.print(t.getNumber() + " ");
		inOrderHelper(t.getRight());
		} else
			System.out.print("EMPTY");
	}

	public void insert(int x){
		insertData(x, root);
	}
	
	
	private void insertData(int n, Node p){
		if(p == null){
			p = new Node(n);
			System.out.print(p.getNumber() + " Inserted in Root ");
		} else if(n < p.getNumber()){
			if(p.getLeft() == null){
				p.setLeft(new Node(n));
				//System.out.print(p.getNumber() + " ");
			} else {
				p = p.getLeft();
				insertData(n,p);
			}
		} else {
			if(p.getRight() == null){
				p.setRight(new Node(n));
				//System.out.print(p.getNumber() + " ");
			} else {
				p = p.getRight();
				insertData(n, p);
			}
		}
	}
	
}

//Driver

import java.util.*;
public class BSTDrive{
	public static void main(String[] args){
		BST tree = new BST();
		Scanner scan = new Scanner(System.in);
		for(int i = 0; i <4; i++){
			System.out.print("Enter Int: ");
			int num;
			num = scan.nextInt();
			tree.insert(num);
			tree.inOrder();
		}
	
	}
}

Here is a sample output that I get (along with the error). It's stating nullpointerexception but I clearly placed a value in the root node. :confused:

Enter Int: 5
5 Inserted in Root EMPTYException in thread "main" java.lang.NullPointerException
	at BST.inOrder(BST.java:19)
	at BSTDrive.main(BSTDrive.java:11)

So as you can see, the insertData method did run and I was able to get it to print the value for p (5) which is supposed to be root. Yet when it comes to the inOrderHelper method it's saying root is empty and jumps straight to print out "EMPTY"

You don't set the root value

private void insertData(int n, Node p){
if(p == null){
	p = new Node(n);
	System.out.print(p.getNumber() + " Inserted in Root ");
} else if(n < p.getNumber()){

should be

private void insertData(int n, Node p){
if(p == null){
	p = new Node(n);
	root = p;
	System.out.print(p.getNumber() + " Inserted in Root ");
} else if(n < p.getNumber()){

Awesome! thanks a lot, that certainly did the trick.
However, I am now running in to the issue where each time I add a node, it's only inserting from that point. Say I add these values in this order: [12 8 16 3 5]
The tree is going to look like this

_________12
______8_____16
___3
______5

//Ignore the underscore lines... i couldn't get this thing to format my tree correctly using spaces haha
Instead, its supposed to have the numbers 3 and 5 as children of number 8.

Any thoughts?

Edited 6 Years Ago by whoadiz: n/a

That looks correct. The way a BST works is it has 2 nodes (that it cares about) left and right. The left node will always be smaller then its parent, while the right node will either be equal to or larger then the parent. In order for search to work these need to be accounted for.

In your case with the tree looking like this and the number 5 being added:

_________12
______8_____16
___3

The algorithm will go though these steps:

  1. Is 5 < 12 ... Yes (left sub tree)
  2. Is 5 < 8 ... Yes (left sub tree)
  3. Is 5 < 3 ... No (right sub tree)
  4. Since there are no other checks it would add it into this spot

And the resulting tree would look like

_________12
______8_____16
___3
______5

(Same as you showed)

Hope that helps

Thanks for that last reply, I guess I had been staring at the code for so long I forgot how to do simple number comparisons haha

Anyways, I've got most of my everything done but I am stuck on this one part when I try to remove a node.

public void remove(int n){
		removeHelper(n, root);
	}
	
	private static  Node removeHelper(int n, Node t){
		if(t !=null){
			if(t.getNumber() < n){
				t.setRight(removeHelper(n, t.getRight()));
			} else if (t.getNumber() > n){
				t.setLeft(removeHelper(n, t.getLeft()));
			} else {
				if (t.getLeft() == null && t.getRight() == null){
					t = null;
				} else if (t.getLeft() != null && t.getRight() == null) {
					t = t.getLeft();
				} else if (t.getRight() != null && t.getLeft() == null) {
					t = t.getRight();
				} else {
					if(t.getRight().getLeft() == null){
						Node r = t.getRight();
						r.setLeft(t.getLeft());
						t = t.getRight();
					} else {
						Node q, p = t.getRight();
						while (p.getLeft().getLeft() != null)
							p = p.getLeft();
						q = p.getLeft();
						p.setLeft(q.getRight());
						q.setLeft(t.getLeft());
						q.setRight(t.getRight());
						t = q;
					}

				}
			}
		}
		return t;
	}

Everything works correctly, except when i try to remove the root it does something funky and actually adds more nodes??

Here's a sample run:

Enter Int: 12
Enter Int: 8
Enter Int: 16
Enter Int: 3
Enter Int: 5
3 5 8 12 16   
Height is: 4 Smallest Value is :3 Size is  : 5
Enter Num to remove: 12
3 5 8 12 3 5 8 16   
Height is: 5 Smallest Value is :3 Size is  : 8

I am fairly certain that it's something in this section of the code but I can't seem to figure where I went wrong?

if(t.getRight().getLeft() == null){
   Node r = t.getRight();
   r.setLeft(t.getLeft());
   t = t.getRight();

Removing is typically the hardest part of the BST. In order to do this the easiest I changed up your code slightly. Instead of having the tree do the work for adding / removing, I used the node to do so.

Moved the insert method into the node and modified the tree's insert method.

/**
 * Inserts a value into the tree
 * @param value the value to insert
 * @return true if the value was added successfully; false otherwise
 */
public boolean insert(int value)
{
	boolean result = false;
	if(value == number)
		result = false;
	else if(value < number)
	{
		if(left == null)
		{
			left = new Node(value);
			result = true;
		}
		else
			result = left.insert(value);
	}
	else if(value > number)
	{
		if(right == null)
		{
			right = new Node(value);
			result = true;
		}
		else
			result = right.insert(value);
	}
	return result;
}
public boolean insert(int x)
{
	boolean result = false;
	if(root == null)
	{
		root = new Node(x);
		result = true;
	}
	else
		result = root.insert(x);
	
	return result;
}

In the above you will notice a boolean being returned so error handling is easier

I added a utility method to the node class to get the minimum value
of a segment of the tree (since each node is a tree itself)

public int minValue()
{
	int result = Integer.MIN_VALUE;
	if(left == null)
		result = number;
	else
		result = left.minValue();
	
	return result;
}

Min value is then used in the remove method

public Node remove(int value, Node parent)
{
	Node toReturn = null;
	if(value < number)
	{
		//need to go down the left tree
		if(left != null)
			toReturn = left.remove(value, this);
		else
			toReturn = null;
	}
	else if(value > number)
	{
		//need to go down the right tree
		if(right != null)
			toReturn = right.remove(value, this);
		else
			toReturn = null;
	}
	else
	{
		//we found the node
		if(left != null && right != null)
		{
			//set the value of this node to the minimum on the
			//right side
			number = right.minValue();
			right.remove(this.number, this);
		}
		else if(parent.left == this)
		{
			//the parents left node is our node
			if(left != null)
				parent.left = left;
			else
				parent.left = right;
			
			//this could be written as:
			//parent.left = (left != null) ? left : right;
		}
		else if(parent.right == this)
		{
			parent.right = (left != null) ? left : right;
		}
	}
	return toReturn;
}

Then the BST class

public Node remove(int n)
{
	if(root == null)
		return null;
	else
	{
		if(root.getNumber() == n)
		{
			Node auxRoot = new Node(0);
			auxRoot.setLeft(root);
			Node result = root.remove(n, auxRoot);
			root = auxRoot.getLeft();
			return result;
		}
		else
		{
			return root.remove(n, null);
		}
	}
}

I hope that helps to clear it up. Look through the code and run it though the debugger and try and understand what is happening. If you have some problems I am more then happy to help out.

Cheers

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