-
My recursive problem
So I'm trying to find the height of my Binary Search Tree using a recursive method. Here is my code for my Tree data structure
Code:
package Structures;
import java.util.NoSuchElementException;
public class ArrayBinarySearchTree<T extends Comparable<T>> implements BinarySearchTreeADT<T>
{
//private Object[] dataStorage = new Object[10]; use this
private BinaryTreeNode<T> root = new BinaryTreeNode<T>();
private int counter = 0;
//method complete
@Override
public void addElement(T element)
{
if (counter == 0)
{
BinaryTreeNode<T> node = new BinaryTreeNode<T>(element);
root = node;
counter++;
}
else
{
addHelp(root, element);
}
}
//method complete
@Override
public boolean contains(T targetElement)
{
BinaryTreeNode<T> node = new BinaryTreeNode<T>();
node = root;
boolean temp = recursiveContainsSearch(node, targetElement);
return temp;
}
//method complete
@Override
public T find(T targetElement)
{
BinaryTreeNode<T> node = new BinaryTreeNode<T>();
node = root;
if(!recursiveContainsSearch(node, targetElement)) {
throw new NoSuchElementException("The element "+targetElement+" does not excist in this tree");
} else {
return recursiveElementFind(node, targetElement);
}
}
//method complete
@Override
public T findMax()
{
BinaryTreeNode<T> node = new BinaryTreeNode<T>();
node = root;
return recursiveFindMax(node);
}
//method complete
@Override
public T findMin()
{
BinaryTreeNode<T> node = new BinaryTreeNode<T>();
node = root;
return recursiveFindMin(node);
}
//method complete
@Override
public boolean isEmpty()
{
if (counter == 0)
return true;
return false;
}
@Override
public Iterator<T> iteratorLevelOrder()
{
// TODO Auto-generated method stub
return null;
}
@Override
public Iterator<T> iteratorOrdered()
{
// TODO Auto-generated method stub
return null;
}
@Override
public Iterator<T> iteratorPostOrder()
{
// TODO Auto-generated method stub
return null;
}
@Override
public Iterator<T> iteratorPreOrdered()
{
// TODO Auto-generated method stub
return null;
}
@Override
public T removeElement(T targetElement)
{
// TODO Auto-generated method stub
return null;
}
@Override
public T removeMax()
{
// TODO Auto-generated method stub
return null;
}
@Override
public T removeMin()
{
// TODO Auto-generated method stub
return null;
}
@Override
public int size()
{
return counter;
}
//helper methods
private void addHelp(BinaryTreeNode<T> n, T element) {
if((element.compareTo(n.getElement()) <= 0) && (n.getLeft() != null))
addHelp(n.getLeft(), element);
if((element.compareTo(n.getElement()) > 0) && (n.getRight() != null))
addHelp(n.getRight(), element);
if((element.compareTo(n.getElement()) <= 0) && (n.getLeft() == null)) {
BinaryTreeNode<T> node = new BinaryTreeNode<T>(element);
n.setLeft(node);
counter++;
}
if((element.compareTo(n.getElement()) > 0) && (n.getRight() == null)) {
BinaryTreeNode<T> node = new BinaryTreeNode<T>(element);
n.setRight(node);
counter++;
}
}
//use to build array
public void buildArray() {
}
public int heightTester() {
BinaryTreeNode<T> node = new BinaryTreeNode<T>();
node = root;
return recursiveHeight(node);
}
public int recursiveHeight(BinaryTreeNode<T> n) {
if((n.getLeft() == null) && (n.getRight() == null)) // HERE IS WHERE THE PROBLEM LIES!!!!!!!
return 0;
int left = 0;
int right = 0;
if(n.getLeft() != null)
return recursiveHeight(n.getLeft()) + 1;
if(n.getRight() != null)
return recursiveHeight(n.getLeft()) + 1;
if(left < right)
return right;
return left;
}
//helper for "public boolean contains(T targetElement)"
private boolean recursiveContainsSearch(BinaryTreeNode<T> n, T element) {
if((element.compareTo(n.getElement()) < 0) && (n.getLeft() != null))
return recursiveContainsSearch(n.getLeft(), element);
if((element.compareTo(n.getElement()) > 0) && (n.getRight() != null))
return recursiveContainsSearch(n.getRight(), element);
if((element.compareTo(n.getElement()) == 0))
return true;
if((element.compareTo(n.getElement()) < 0) && n.getLeft() == null)
return false;
else if((element.compareTo(n.getElement()) > 0) && n.getRight() == null)
return false;
return false;//should be no other options
}
//helper for "public T find(T targetElement)"
private T recursiveElementFind(BinaryTreeNode<T> n, T element) {
if((element.compareTo(n.getElement()) < 0) && n.getLeft() != null)
return recursiveElementFind(n.getLeft(), element);
if((element.compareTo(n.getElement()) > 0) && n.getRight() != null)
return recursiveElementFind(n.getRight(), element);
if(element.compareTo(n.getElement()) == 0)
return n.getElement();
return null;
}
//helper for "public T findMin()"
private T recursiveFindMin(BinaryTreeNode<T> n) {
if(n.getLeft() != null)
return recursiveFindMin(n.getLeft());
return n.getElement();
}
//helper for "public T findMax()"
private T recursiveFindMax(BinaryTreeNode<T> n) {
if(n.getRight() != null)
return recursiveFindMax(n.getRight());
return n.getElement();
}
} //end class
So when trying to find the height of my tree using the heightTester() method which uses the recursiveHeight(BinaryTreeNode<T> n) method in the line that calls the
recursiveHeight method it should pass the root node to the method. Here is where this gets very weird. Running debug on Eclipse I see that sometimes it actually does pass the node
and sometimes it doesn't. Sometimes it makes it in the recursiveHeight method and recursively loops once but then I get a null pointer exception at the line of code
Code:
if((n.getLeft() == null) && (n.getRight() == null))
Here is the client code im using to test my tree
Code:
package projectmain;
import Structures.ArrayBinarySearchTree;
public class TesterMain
{
public static void main(String[] args) {
ArrayBinarySearchTree<Integer> tester = new ArrayBinarySearchTree<Integer>();
tester.addElement(20);
tester.addElement(15);
tester.addElement(13);
tester.addElement(14);
tester.addElement(25);
tester.addElement(33);
tester.addElement(39);
tester.addElement(21);
tester.addElement(17);
tester.addElement(31);
System.out.println(tester.size());
System.out.println(tester.heightTester());
}
}
This should produce the tree which looks like
20
/ \
15 25
/ \ / \
13 17 21 33
\ / \
14 31 39
Thanks in advance for all your help.