title: How does this BST node-deletion algorithm work?
body: <p>I'm trying to follow the BST algorithm in <a href="http://dotnetslackers.com/projects/Data-Structures-And-Algorithms/" rel="nofollow">"Data Structures and Algorithms" by Granville Barnett</a>, but I don't understand the node-deletion algorithm it describes below.</p>
  
  <p>Section 3.3 (p. 22)</p>
  
  <blockquote>
    <p>Removing a node from a BST is fairly straightforward, with four cases to consider:</p>
    
    <ol>
    <li>the value to remove is a leaf node; or</li>
    <li>the value to remove has a right subtree, but no left subtree; or</li>
    <li>the value to remove has a left subtree, but no right subtree; or</li>
    <li>the value to remove has both a left and right subtree in which case we promote the largest value in the left subtree.</li>
    </ol>
  </blockquote>
  
  <p>Figure 3.2 (p. 22)</p>
  
  <pre><code>    23
     /  \
    14   31
   /
  7
   \
    9
  </code></pre>
  
  <ul>
  <li>Case #1 points to node 9.</li>
  <li>Case #2 points to node 7.</li>
  <li>Case #3 points to node 14.</li>
  <li>Case #4 points to node 23.</li>
  </ul>
  
  <p>I interpret the text above for #4 to mean that when we remove 23, we promote 14 to root and make 31 its right child:</p>
  
  <pre><code>  14
   /  \
  7   31
   \
    9
  </code></pre>
  
  <p>...but the book's algorithm (from p. 23) for case #4 bamboozles me (I've rewritten it here in Java):</p>
  
  <pre><code>1 boolean remove(T value) {
  2   // ...
  3
  4   // case #4
  5   Node largestValueNode = nodeToRemove.left;
  6   while (largestValueNode.right != null) {
  7       // find the largest value in the left subtree of nodeToRemove
  8       largestValueNode = largestValueNode.right;
  9   }
  10  
  11  // delete the right child of largestValueNode's parent
  12  findParent(largestValueNode.value).right = null;
  13  nodeToRemove.value = largestValueNode.value;
  14  
  15  count--;
  16  return true; // successful
  17}
  </code></pre>
  
  <p>If I follow the algorithm, the <code>largestValueNode</code> is node 14, so its parent is node 23. <strong>Why does the algorithm nullify the right child of the parent?</strong></p>
  
  <p><strong>Why does line 13 copy the <code>largestValueNode</code>'s value into the node to be deleted?</strong></p>
  
  <p>I would've expected lines 11-13 to be:</p>
  
  <pre><code>11  if (largestValueNode != null)
  12      largestValueNode.right = nodeToRemove.right;
  13  nodeToRemove.right = null;
  </code></pre>
  
  <p><strong>EDIT:</strong></p>
  
  <p>The book's algorithm indeed has a bug. The fix is below:</p>
  
  <pre><code>1 boolean remove(T value) {
  2   // ...
  3
  4   // case #4
  5   Node largestValueNode = nodeToRemove.left;
  6   while (largestValueNode.right != null) {
  7       // find the largest value in the left subtree of nodeToRemove
  8       largestValueNode = largestValueNode.right;
  9   }
  10  
  11  Node p = findParent(largestValueNode.value);
  12  if (p != null) {
  13      if (nodeToRemove == p)
  14          nodeToRemove.left = largestValueNode.left;
  15      else
  16          p.right = largestValueNode.left;
  17  }
  18  nodeToRemove.value = largestValueNode.value;
  19  
  20  count--;
  21  return true; // successful
  22}
  </code></pre>