[taylor.alison]

Okay. So. I am working on a remove function in a binary search tree. Right now, I am having loads of trouble with one tiny little value. It changes at the last minute, and I have no idea why. I have gone through and through it, and I've decided that I need a fresh pair of eyes to see if they can spot it.

I am using three functions. Again, it is probably not efficient to do this, but I'm just trying to get something working here.


The following method MUST return a "value". It returns the value of the node to be removed, if it is found.

	public V remove(int key) {
		BNode<V> current = root;
		BNode<V> currentNode = recursiveRemoveSearch(key,current);
		System.out.println("In the remove method, the value is: " + currentNode);
		return recursiveRemove(key, currentNode);
	}

public BNode<V> recursiveRemoveSearch(int key, BNode<V> current)
	 {
		 System.out.print("val at start of recursiveRemoveSearch:  " + current.getKey() + ". ");
		 if (key == current.getKey())
			{
				//current = current;
				//current = root;
				return current;
			}
			else if (key < current.getKey())
			{
				current = current.getLeft();
				recursiveRemoveSearch(key, current);
			}
			else if(key > current.getKey())
			{
				current = current.getRight();
				recursiveRemoveSearch(key, current);
			}
		 return current;
	 }

public V recursiveRemove(int key, BNode<V> current)
	 {		
		 //V value = current.getValue();
		 //if(current == null)
		 //{
			 //return null;
		 //}
		 System.out.print("Val at start of recursiveRemove " + current.getKey());
		 BNode<V> tempCurrent = current;
		 if(current.getLeft() == null && current.getRight() == null)
		 {
			 //value = current.getValue();
			 current = null;
			 return tempCurrent.getValue();
			 
		 }
		 else if(current.hasLeft() == true || current.hasRight() == true)
		 {
			  if(current.hasLeft() == true)
			  {
				  BNode<V> currentChild;
				  currentChild = current.getLeft();
				  System.out.println(currentChild + "'s old Parent was: " + currentChild.getParent());
				  currentChild.setParent(current.getParent());
				  System.out.println(currentChild + "'s new Parent is: " + currentChild.getParent());
				  current = null;
				  return tempCurrent.getValue();
				  
			  }
			  else if(current.hasRight() == true)
			  {
				  BNode<V> currentChild;
				  currentChild = current.getRight();
				  System.out.println(currentChild + "'s old Parent was: " + currentChild.getParent());
				  currentChild.setParent(current.getParent());
				  System.out.println(currentChild + "'s new Parent is: " + currentChild.getParent());
				  current = null;
				  return tempCurrent.getValue();
			  }
		 }
		 return tempCurrent.getValue();
	 }

Now what I want to happen so far (for the parts that I have coded) is when I go to remove a key (in my tests, key "8" in a tree of four nodes, 6 as the root, 4 on the left, and 7 on the right with 8 as its child)it should be able to find that key and reset the tree accordingly. HOWEVER, when I ran my tests, this is what happened.
val at start of recursiveRemoveSearch: 6.
val at start of recursiveRemoveSearch: 7.
val at start of recursiveRemoveSearch: 8.
In the remove method, the value is: 7:SEVEN
Val at start of recursiveRemove 7

In the highlighted red section, WHY HAS THE VALUE SUDDENLY CHANGED? It was fine, it should be returning 8....and yet, the recursiveRemove method now has the value 7...I need to get the node with value 8 to it. Can anybody see why this isn't working? I know my code is MESSY but I'm just trying to get something out first

[taylor.alison]

I've tried "removing" other values, and still that value that comes out is always 7. It must be something to do with a return statement...I think I know which one, but I don't know how to fix it

[macosxnerd101]

You have a couple cases you need to consider. First, when your root Node has the target value. This will basically force you to choose either the left or right child as the new Root Node, and then insert the other Node into the Tree.

If the Node with the target value isn't the root, that makes your life a lot easier. From a parent Node, search its children. If you find a match, remove that Node from the Tree, and replace it with one of its children.

So for the overall logic:

remove(Node root, target)
     if root.value = target
           delete root
           set the right node to the new root
           insert the left node
           return
     if target > root.value
           check the right node
           if it isn't the right node's value
                remove(right, target)
           else 
              remove the right node
              replace it with a child of the right node
                 
     else repeat the process for the right node and apply it to the left node