Question

Question 3:

Create a method for the Binary Search Tree (deleteNode) that deletes a specified node identified by its value, and rearranges the descendants of the deleted node to ensure the resulting Tree meets the requirements of a Binary Search Tree.

a) Discuss and justify your approach to address each possible case.

b) Is the new tree (with the deleted node removed) unique? Discuss your answer.

Discuss method's Big-O notation. Add proper and consistent documentation to identify code sections or lines to clearly identify its purpose.

Illustrate the performance of the deleteNode method. Delete 71, 400, 271 938, and 69 from the tree in the same order. For all illustrated examples, enumerate the trees (before and after deletion) using your orderTraversal and justify the correctness of your delete method.

Answer 1

So, in this problem we have the function for deleting the node for binary search tree and after that their desendants will adjust accordingly as you will get clear picture after you go through this function.

// Deleting a node for BST
   public static Node deleteNode(Node root, int key)
   {
       // initializing pointer to zero
       Node parent = null;

       // start with root node
       Node curr = root;

       // search key in BST and set its parent pointer
       while (curr != null && curr.data != key)
       {
           // setting parent as current
           parent = curr;

           // if key is less than curr node then go for left sub tree
           // else go for right sub tree
           if (key < curr.data) {
               curr = curr.left;
           }
           else {
               curr = curr.right;
           }
       }

       // returning the root if key is not found
       if (curr == null) {
           return root;
       }

       // Case 1: if the node is a leaf node
       if (curr.left == null && curr.right == null)
       {
           // if node to be deleted is not a root node, then set its
           // parent left/right child to null
           if (curr != root) {
               if (parent.left == curr) {
                   parent.left = null;
               } else {
                   parent.right = null;
               }
           }
           //given tree has only one node then set it to null
           else {
               root = null;
           }
       }

       // Case 2: if the node has 2 children
       else if (curr.left != null && curr.right != null)
       {
           // find its in-order successor node
           Node successor = minimumKey(curr.right);

//function for minimumkey a helper function

//public static Node minimumKey(Node curr)
// {
// while (curr.left != null) {
// curr = curr.left;
//}
//return curr;
//}

           int val = successor.data;

           // recursively delete the successor. Note that the successor
           // will have at-most one child (right child)
           deleteNode(root, successor.data);

           // Copy the value of successor to current node
           curr.data = val;
       }

       // Case 3: if the node has on child
       else
       {
           // find child node
           Node child = (curr.left != null)? curr.left: curr.right;

           if (curr != root)
           {
               if (curr == parent.left) {
                   parent.left = child;
               } else {
                   parent.right = child;
               }
           }

           // if root to be deleted then set it to the child
           else {
               root = child;
           }
       }

       return root;
   }

most probably we covered it in three cases which will give correct output

-->69,71,400,271938

-->69,400,271938

-->69,271938

-->271938