Trouble with a toy tree [SOLVED]

[Lido Scaggsinsky]

I'm trying to build a basic tree so I can write some test algorithms against it, but I'm getting null pointers and some weird behavior while trying to load the tree with data. Any advice would be appreciated. Is using recursion to find the spot to insert a node a bad idea? What I don't understand is why it's trying to add Lass under Tass, and then after that seems to not go down the right side of the tree and starts placing nodes right under the root ("Mass"). Thanks. Three classes will follow:

Node:

public class Node<V> {

	private Node<V> left;
	private Node<V> right;
	private V value;

	Node ( V value ) {
		this.value = value;
	}

	public void addLeft ( Node<V> node ) {
		left = node;
	}

	public void addRight ( Node<V> node ) {
		[color=red]left[/color] = node;
	}

	public boolean hasLeft() {
		if ( left != null )
			return true;
		return false;
	}

	public boolean hasRight() {
		if ( right != null )
			return true;
		return false;
	}

	public Node<V> getLeft() {
		return left;
	}

	public Node<V> getRight() {
		return right;
	}

	public V getValue() {
		return value;
	}
}

Tree:

public class Tree<V extends Comparable<V>> {

	private Node<V> root;

	Tree ( V value ) {
		root = new Node<V>( value );
	}

	public void insert( V value ) {
		Node<V> node = new Node<V>( value ); 
		addNode( node, root );
	}

	private void addNode ( Node<V> node, Node<V> start ) {
		System.out.println(node.getValue() + ", " + start.getValue() + ", " +node.getValue().compareTo( start.getValue() ));
		
		if ( node.getValue().compareTo( start.getValue() ) < 0 ) {
			if ( ! start.hasLeft() ) {
				start.addLeft( node );
				System.out.println("Adding " + node.getValue() + " on left under " + start.getValue());
			}
			else
				addNode( node, start.getLeft() );
		}
		else if ( node.getValue().compareTo( start.getValue() ) > 0 )
			if ( ! start.hasRight() ) {
				start.addRight( node );
				System.out.println("Adding " + node.getValue() + " on right under " + start.getValue());
			}
			else
				addNode( node, start.getRight() );
	}

	public void printTree() {
	}
}

TreeTester:

public class TreeTester {

	public static void main(String[] args) {
		Tree<String> tree = new Tree<String>("Mass");
		tree.insert("Bass");
		tree.insert("Cass");
		tree.insert("Tass");
		tree.insert("Lass");
		tree.insert("Sass");
		tree.insert("Zass");
		tree.insert("Gass");
		tree.insert("Fass");
		tree.insert("Wass");
		tree.insert("Hass");
		tree.insert("Nass");
		tree.insert("Xass");
		tree.insert("Dass");
		tree.printTree();
	}

}

[Stephan van Hulst]

Hi, Lido. You should probably make your printTree method recursive, so it will print all the nodes in the tree, and it will prevent your code from throwing NullPointerExceptions.

As for your other problem, your addRight method doesn't seem to be working. Take a good look

[Campbell Ritchie]

A tree will always have nulls in. So when you are iterating the tree, recursively, using an inorder depth-first traversal, you would do it like this

1: See whether the left value is null

2: If it is null, do nothing with it.

3: If it wasn't null, pass this method recursively to the left.

4: Print the "value" field.

5: See whether the "right" field is null.

6: If it was null, leave it alone.

7: If it wasn't null, pass this method to it recursively

That would look something like this

public void inorderDisplay(Node n)
{
    if (left != null)
    {
        inorderDisplay(left)
    }
    System.out.println(value);
    if (right != null)
    {
        inorderDisplay(right);
   }
}

By the way, your hasLeft() method is poor style. It would be far better to write

public boolean hasLeft()
{
   return left != null;
}

The generic form is <T extends Comparable<? super T>>

[Lido Scaggsinsky]

Stephan van Hulst wrote:Hi, Lido. You should probably make your printTree method recursive, so it will print all the nodes in the tree, and it will prevent your code from throwing NullPointerExceptions.

As for your other problem, your addRight method doesn't seem to be working. Take a good look

Ha! Thanks! No wonder....

Yeah, that print method was just some sloppy debugging.

[Lido Scaggsinsky]

Campbell Ritchie wrote:By the way, your hasLeft() method is poor style. It would be far better to write

public boolean hasLeft()
{
   return left != null;
}

The generic form is <T extends Comparable<? super T>>

Thanks, that hasLeft() does look cleaner.

What is the difference between the generic form and what I used in my Tree class?

public class Tree<V extends Comparable<V>>

[Stephan van Hulst]

Campbell's form is more flexible. It won't change the way your method works, but it will allow the client to use more argument types.

For instance, if you have a class Fruit extends Comparable<Fruit>, and you have a class Pear extends Fruit, then your current method will only be able to accept Fruits, and not Pears. Using the wildcard, your method can take Pears as well, without any extra effort on your part.

[Campbell Ritchie]

It's not my form; it's what it says in the API when you look up Comparable.

[Lido Scaggsinsky]

Stephan van Hulst wrote:Campbell's form is more flexible. It won't change the way your method works, but it will allow the client to use more argument types.

For instance, if you have a class Fruit extends Comparable<Fruit>, and you have a class Pear extends Fruit, then your current method will only be able to accept Fruits, and not Pears. Using the wildcard, your method can take Pears as well, without any extra effort on your part.

Perfect, thanks!