traversing an ordered binary tree

[Johnny Steele]

Hi,

Im trying to build a method that adds a node to this tree. It takes arguments, a number representing the order at which this node needs to be placed in the tree, and the element that the node is to contain.

so for example,

..............25
............./...\
.........16......50
......./...\.........\
...14....20........75

so if I were to add the number 30 it would be at 50.left

if there is a matching duplicate number, I have to return the element of the node being replaced.

this is what I have so far...
its not wright but its a start.
I'm getting nullPointerExceptions on my tests so far.

any advice?

  public V put(K key, V newValue) {
	  MapNode current = root;
	  MapNode previous = root;
	  MapNode temp;
	  
	  
		  
		
		while(current != null) { 
			if(key.compareTo(current.key) < 0) {
				previous = current;
				current = current.left;
				
			}else if(key.compareTo(current.key) > 0){
				previous = current;
				current = current.right;
			}else if(key.equals(current.key)){
				temp = current;
				current = new MapNode(key, newValue);
				return temp.value;

			}
		}  				current = new MapNode(key, newValue);
		                                return null;
}
		 
		  

thanks

[Stephan van Hulst]

I suggest you use a recursive method.

Hint: inserting a node in a tree, is the same as inserting the node in either the left or the right subtree, depending on how the node compares to the parent's key.

[Johnny Steele]

got it!!! I figured it out. thanks!!!