Updating the deletion path in a BST
<p>I am hoping to get some input here. I have built a 2-dimenstional binary search tree class. I have all operations (insert, delete etc.) working as they should. I have run into a problem that I can't seem to get around. I currently have data members in each node, that must be updated within the deletion path (relative height, extrema values for respective sub-tree, etc). The problem is, I need my delete method to return a boolean value which represents it being successful. Meaning, if the node doesn't exist, false is returned. Otherwise true. 
I am solving this recursively, so when I come out of each function call, I am updating values</p>

<p>The get a basic idea of what is going on, here is what delete looks like:</p>

<pre><code>private boolean delete (Node n, Value val, boolean cut) {
   // Base case
   if(n == null) return false;
   if(node to be deleted) {
        // Do all sorts of swapping, recursive deletion calls
   }
   else {
       // Move around the tree until I find a node or hit null
       if(is in left subtree)
         delete(t.left, val, !cut);
       if(is in right subtree)
         delete(t.right, val, !cut);
   }

   // Here is where updating happens
   someUpdateFunction(n);

   // Now java here is forcing me to return something, so I have to return true or false  
   return true;
}
</code></pre>

<p>So my problem is that I am always returning true, since this code always executes. Does anybody have any ideas of how I can update my deletion path, and still be able to return false if the node does not exist?
Thanks for any input.</p>
