@@ -0,0 +1,2593 @@
+package com.freetymekiyan.algorithms.other;%0A%0Aimport com.freetymekiyan.algorithms.utils.Utils.TreeNode;%0A%0A/**%0A * Given a root of BST and a node's value. Delete the node with that value from the tree.%0A * Return new root.%0A * %3Cp%3E%0A * Tags: Tree%0A */%0Apublic class DeleteANodeFromBinarySearchTree %7B%0A%0A    /**%0A     * Tree. BST. Recursive. The Hibbard deletion.%0A     * Two stages: Search for the node while tracking the parent.%0A     * If the node is found, delete.%0A     * Recursive delete will take the root and return new root.%0A     * So that the subtree can be connected to its parent.%0A     * Base case:%0A     * When root is null, return null.%0A     * Recurrence relation:%0A     * If key %3C root.val, key is in left subtree.%0A     * %7C Recurse on the left subtree and update root.left with the result.%0A     * If key %3E root.val, key is in right subtree.%0A     * %7C Recurse on the right subtree and update root.right with the result.%0A     * Else key == root.val, the node is found, start to delete.%0A     * %7C If root is a leaf, return null.%0A     * %7C If root has one child, return that child.%0A     * %7C That combines to:%0A     * %7C   If root.left == null, return root.right.%0A     * %7C   Else if root.right == null, return root.left.%0A     * %7C Now root has two children. Find the in-order successor or predecessor.%0A     * %7C First replace root's value with the minimum value of right subtree.%0A     * %7C Then delete the value from right subtree with recursive call.%0A     * Return root.%0A     * http://quiz.geeksforgeeks.org/binary-search-tree-set-2-delete/%0A     */%0A    public TreeNode delete(int key, TreeNode root) %7B%0A        if (root == null) %7B%0A            return null;%0A        %7D%0A        if (key %3C root.val) %7B%0A            root.left = delete(key, root.left);%0A        %7D else if (key %3E root.val) %7B%0A            root.right = delete(key, root.right);%0A        %7D else %7B // Key is same as current root's val.%0A            // Node with only one child or no child.%0A            if (root.left == null) %7B%0A                return root.right;%0A            %7D else if (root.right == null) %7B%0A                return root.left;%0A            %7D%0A            // Node with two children: Get the inorder successor.%0A            root.val = getMin(root.right);%0A            // Delete the inorder successor.%0A            root.right = delete(root.val, root.right);%0A        %7D%0A        return root;%0A    %7D%0A%0A    /**%0A     * Find the minimum value of BST.%0A     */%0A    private int getMin(TreeNode root) %7B%0A        int min = root.val;%0A        while (root.left != null) %7B%0A            min = root.left.val;%0A            root = root.left;%0A        %7D%0A        return min;%0A    %7D%0A%7D%0A

add delete a node from BST