# My recursive problem

• 11-18-2011, 04:08 AM
seanfmglobal
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
{
if (counter == 0)
{
BinaryTreeNode<T> node = new BinaryTreeNode<T>(element);
root = node;
counter++;
}
else
{

}
}

//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))
if((element.compareTo(n.getElement()) > 0) && (n.getRight() != null))
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>();

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