Binary Tree

[sqeezon]

After doing as much testing as I am capable of I must turn to the good folks of the forums for assistance. I'm creating a binary tree in Java with all the normal tree functions (insert, delete, print). The delete method I have written is giving me trouble. Here is the method.

 //Recursive helper method which calls delete method
	public void delete(String key) {
		delete(root, key);
	}
	
	
	/* Method used to delete items from BTree
	 * 3 Cases: 
	 * 		1 -  Node has no children, in which case it is replaced by a null node
	 * 		2 -  Node has 1 child either to the left or right, in which case it is replaced by that node
	 * 		3 -  Node is a root with 2 children. This node is saved as dltNode and dltNodes data is replaced by the data
	 * 			 of the largest item in dltNode's left subtree. Then delete method is called recursively to delete the largest
	 * 			 node in the left subtree.
	 */
	private void delete(Node current, String dltkey) {
			
		
		if(dltkey.compareTo(current.data) < 0)
			delete(current.left , dltkey);
		else if (dltkey.compareTo(current.data) > 0)
			delete(current.right, dltkey);		
		else {		
			 if(current.left == null) {								 
				 current = current.right;				
			 }
			 else if(current.right == null) {				
				 current = current.left;			 
			 }
			 else {
				 Node dltnode;
				 dltnode = current;				
				 Node largest = findLargest(dltnode.left);
				 dltnode.data = largest.data;
				 delete(dltnode.left, largest.data);
			 }
		}
	}

The problem is when a node has no children. It should set the current node to its null child but it does not. Assuming all the other method this delete method relies upon such as insertion and finding max work, can anyone see why deleting a node with no children would not work?

 

[LuminaryJanitor]

if(current.left == null) {
	current = current.right;
}
else if(current.right == null) {
	current = current.left;
}

This is the bit you're talking about?

If the node is a leaf then current.left==null, and so current is set to current.right, which is also null. So now you have a local variable called current with a value of null, and then you return, and discard this variable, without making any modification to the tree. You'll probably find that this'll screw up for nodes with one child too.

You'll want to keep track of the previous node to sort this out.

One more thing... you're missing the base case for when the key isn't there.

 

[sqeezon]

Yes, that is the bit I'm talking about. I see what you are saying. Now I will see if I can fix it.