Delete from BST
by Isai Damier, Android Engineer @ Google

/*************************************************************************
 * Author: Isai Damier
 * Title: Delete
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Time Complexity of Solution:
 *   Best = const; Average = O(log(n)); Worst = O(n).

 * Technical Details:
 *    1] find node to be removed and track its parent
 *    2] if node == null then return null (element is not in tree)
 *    3] declare 'replacement' Node
 *    4] if node has both children
 *     - delete node's successor
 *     - give custody of node's children to successor
 *     - set replacement to successor
 *    5] if node has fewer than two children
 *     - set replacement to node's child
 *    6] if node is root then set replacement to root (new root)
 *    7] else replacement becomes child of node's parent
 *
 ************************************************************************/ 
 public Node delete(int el) {
  //find node and it's parent
  Node node = root, parent = null;
  while (null != node && el != node.data) {
    parent = node;
    if (el > node.data) {
      node = node.right;
    } else {
      node = node.left;
    }
  }
  //if node is null return null
  if (null == node) {
    return null;
  }
  //declare replacement
  Node replacement;
  //if node has two children
  if (null != node.left && null != node.right) {
    replacement = removeSuccessor(node);
    replacement.left = node.left;
    replacement.right = node.right;
  }//if node has one or no child
  else if (null == node.left) {
    replacement = node.right;
  } else {
    replacement = node.left;
  }

  //replace node
  if (node == root) {
    root = replacement;
  } else if (parent.left == node) {
    parent.left = replacement;
  } else {
    parent.right = replacement;
  }
  return node;
}//delete(int)

private Node removeSuccessor(Node n) {
  //it is known that n has a right child
  Node succ = n.right, parent = n;
  while (null != succ.left) {
    parent = succ;
    succ = succ.left;
  }
  //a successor has no left child
  if (succ == parent.right) {
    parent.right = succ.right;
  } else {
    parent.left = succ.right;
  }
  return succ;
}//removeSuccessor(Node)

import java.io.ByteArrayOutputStream;
import java.io.FileDescriptor;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import org.junit.Test;
import static org.junit.Assert.*;

public class BSTTest {

 /**
   * Test of delete method, of class BST.
   */
  @Test
  public void testDelete() {
    System.out.println(""delete"");
    final ByteArrayOutputStream output = new ByteArrayOutputStream();
    System.setOut(new PrintStream(output));

    BST bst = new BST();
    //add elements to tree
    Integer[] treeTape = {200, 100, 300, 50, 150, 250, 350, 25, 75, 125,
      175, 225, 275, 325, 375, 35, 212, 312, 400};

    for (int i : treeTape) {
      bst.add(i);
    }

    //assert the elements are all on the tree
    assertFalse(bst.isEmpty());
    assertEquals(treeTape.length, bst.size());

    for (int i : treeTape) {
      assertEquals(i, bst.find(i).data);
    }

    //for each element deleted, assert that it is not on the tree
    //and that the tree ordering is not disturbed
    int max = treeTape.length;
    List<Integer> sortedRemnant = new ArrayList<Integer>();
    for (int i : treeTape) {
      sortedRemnant.add(i);
    }
    Collections.sort(sortedRemnant);
    String expected = """";

    for (int i : treeTape) {
      assertEquals(i, bst.delete(i).data);//delete the correct data
      assertNull(bst.delete(i));//data has indeed being deleted
      assertEquals(--max, bst.size());//tree shrunk by 1
      sortedRemnant.remove(Integer.valueOf(i));
      bst.inorder();// assume each visit prints to the console
      for (int r : sortedRemnant) {
        expected += r + ""\n"";
      }
      assertEquals(expected, output.toString());//check ordering of tree
    }//for

    assertTrue(bst.isEmpty());//is empty
    assertEquals(0, bst.size());//size is zero
    System.setOut(new PrintStream(new FileOutputStream(FileDescriptor.out)));
    System.out.println(""done with delete"");
  }
}