Delete in binary tree

Delete the target key K in the given binary search tree if the binary search tree contains K. Return the root of the binary search tree.

Find your own way to delete the node from the binary search tree, after deletion the binary search tree's property should be maintained.

Assumptions

• There are no duplicate keys in the binary search tree

  The smallest larger node is first candidate after deletion

Solution: Recursive traversal

case 1: node to delete no children //sever parent-> to node

case 2: no left child //re-attach right child to parent

case 3: no right child //re-attach left child to parent

case 4: both left and right child //A node from left or right tree will need to replace it //largest from right or smallest from left

/**
 * public class TreeNode {
 *   public int key;
 *   public TreeNode left;
 *   public TreeNode right;
 *   public TreeNode(int key) {
 *     this.key = key;
 *   }
 * }
 */
public class Solution {
  public TreeNode deleteTree(TreeNode root, int key) {
    if (root == null){
      return null;
    }
    if (key == root.key){ //if found
      if (root.left == null){
        return root.right;
      } else if (root.right == null){
        return root.left;
      } else if (root.right.left == null){
        root.right.left = root.left;
        return root.right;
      } else {
        TreeNode newRoot = deleteSmallest(root.right);
        newRoot.left = root.left;
        newRoot.right = root.right;
        return newRoot;
      }
    }
    if (key < root.key){
      root.left = deleteTree(root.left, key);
    } else if (key > root.key){
      root.right = deleteTree(root.right,key);
    }
    return root;
  }

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

TC: