2.3 Delete in BST

Assumption: The tree is not balanced. No duplicate in the tree. The smallest larger node is first candidate after deletion

Input: TreeNode root, int target

Output: TreeNode root after deleting node with target value

Solution:

Key: when deleting, make sure to cut the target from its parent

when adding new child, make sure to connect new child to original parent

e.g. Delete (root, 8)

Step 1: Find the node to be deleted

Step 2: Consider 4 situations after deletion Case 1: The node found has no child

Case 2: The node has no left child

Case 3: The node has no right child

Case 4: The node has both children, but

Case 4.1 node.right has no left child, find the largest in left subtree or smallest in right subtree, in this case, move up node.right

Case 4.2 node.right has both children, need to find the smallest node (on the left subtree and not null) and move it up. Make sure that the children of the node being moved up are connected to node.parent

TC: find(upper part of height) + findSmallest(lower part of height) = O(height)

SC: on stack find() = O(height)

public TreeNode delete(TreeNode root, int target) {
  if (root == null) { return root; }
  if (root.key == target) {
    if (root.left == null) {		//case 1 & 2 combined
      return root.right;
    } else if (root.right == null) {
      return root.left;		//case 3
    } else if (root.right.left == null) {	//case 4.1
      root.right.left = root.left;
      return root.right;
    } else {  	//case 4.2
      TreeNode smallest = findSmallest(root.right);
      smallest.left = root.left;
      smallest.right = root.right;
      return smallest;
    }
  }
  if (root.key > target) {
    root.left = delete(root.left, key);
  } else if (root.key < target) {
    root.right = delete(root.right, key);
  }
  return root;
}

private TreeNode findSmallest(TreeNode root) {
  while (root.left.left != null) {
    root = root.left;
  }
  TreeNode smallest = root.left;
  root.left = root.left.right;
  return smallest;
}