When we delete a node, three possibilities arise. 1) Node to be deleted is leaf:
ID: 3910143 • Letter: W
Question
When we delete a node, three possibilities arise.
1) Node to be deleted is leaf: Simply remove from the tree.
2) Node to be deleted has only one child: Copy the child to the node and delete the child
3) Node to be deleted has two children: Find inorder successor of the node. Copy contents of the inorder successor to the node and delete the inorder successor. Note that inorder predecessor can also be used.
Please include as many comments as possible to the source code shown below. For example, for the following method I will add some comments to give clarity to the source code.
//Node method
public Node(int item)
{
key = item; //Set key equal to the item given
left = right = null; //Set the left child and the right child equal to null
}
// Java program to demonstrate delete operation in binary search tree
class BinarySearchTree
{
/* Class containing left and right child of current node and key value*/
class Node
{
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
// Root of BST
Node root;
// Constructor
BinarySearchTree()
{
root = null;
}
// This method mainly calls deleteRec()
void deleteKey(int key)
{
root = deleteRec(root, key);
}
/* A recursive function to insert a new key in BST */
Node deleteRec(Node root, int key)
{
/* Base Case: If the tree is empty */
if (root == null) return root;
/* Otherwise, recur down the tree */
if (key < root.key)
root.left = deleteRec(root.left, key);
else if (key > root.key)
root.right = deleteRec(root.right, key);
// if key is same as root's key, then This is the node
// to be deleted
else
{
// node with only one child or no child
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
// node with two children: Get the inorder successor (smallest
// in the right subtree)
root.key = minValue(root.right);
// Delete the inorder successor
root.right = deleteRec(root.right, root.key);
}
return root;
}
int minValue(Node root)
{
int minv = root.key;
while (root.left != null)
{
minv = root.left.key;
root = root.left;
}
return minv;
}
// This method mainly calls insertRec()
void insert(int key)
{
root = insertRec(root, key);
}
/* A recursive function to insert a new key in BST */
Node insertRec(Node root, int key)
{
/* If the tree is empty, return a new node */
if (root == null)
{
root = new Node(key);
return root;
}
/* Otherwise, recur down the tree */
if (key < root.key)
root.left = insertRec(root.left, key);
else if (key > root.key)
root.right = insertRec(root.right, key);
/* return the (unchanged) node pointer */
return root;
}
// This method mainly calls InorderRec()
void inorder()
{
inorderRec(root);
}
// A utility function to do inorder traversal of BST
void inorderRec(Node root)
{
if (root != null)
{
inorderRec(root.left);
System.out.print(root.key + " ");
inorderRec(root.right);
}
}
// Driver Program to test above functions
public static void main(String[] args)
{
BinarySearchTree tree = new BinarySearchTree();
/* Let us create following BST
50
/
30 70
/ /
20 40 60 80 */
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
System.out.println("Inorder traversal of the given tree");
tree.inorder();
System.out.println(" Delete 20");
tree.deleteKey(20);
System.out.println("Inorder traversal of the modified tree");
tree.inorder();
System.out.println(" Delete 30");
tree.deleteKey(30);
System.out.println("Inorder traversal of the modified tree");
tree.inorder();
System.out.println(" Delete 50");
tree.deleteKey(50);
System.out.println("Inorder traversal of the modified tree");
tree.inorder();
}
}
// Java program to demonstrate delete operation in binary search tree
class BinarySearchTree
{
/* Class containing left and right child of current node and key value*/
class Node
{
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
// Root of BST
Node root;
// Constructor
BinarySearchTree()
{
root = null;
}
// This method mainly calls deleteRec()
void deleteKey(int key)
{
root = deleteRec(root, key);
}
/* A recursive function to insert a new key in BST */
Node deleteRec(Node root, int key)
{
/* Base Case: If the tree is empty */
if (root == null) return root;
/* Otherwise, recur down the tree */
if (key < root.key)
root.left = deleteRec(root.left, key);
else if (key > root.key)
root.right = deleteRec(root.right, key);
// if key is same as root's key, then This is the node
// to be deleted
else
{
// node with only one child or no child
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
// node with two children: Get the inorder successor (smallest
// in the right subtree)
root.key = minValue(root.right);
// Delete the inorder successor
root.right = deleteRec(root.right, root.key);
}
return root;
}
int minValue(Node root)
{
int minv = root.key;
while (root.left != null)
{
minv = root.left.key;
root = root.left;
}
return minv;
}
// This method mainly calls insertRec()
void insert(int key)
{
root = insertRec(root, key);
}
/* A recursive function to insert a new key in BST */
Node insertRec(Node root, int key)
{
/* If the tree is empty, return a new node */
if (root == null)
{
root = new Node(key);
return root;
}
/* Otherwise, recur down the tree */
if (key < root.key)
root.left = insertRec(root.left, key);
else if (key > root.key)
root.right = insertRec(root.right, key);
/* return the (unchanged) node pointer */
return root;
}
// This method mainly calls InorderRec()
void inorder()
{
inorderRec(root);
}
// A utility function to do inorder traversal of BST
void inorderRec(Node root)
{
if (root != null)
{
inorderRec(root.left);
System.out.print(root.key + " ");
inorderRec(root.right);
}
}
// Driver Program to test above functions
public static void main(String[] args)
{
BinarySearchTree tree = new BinarySearchTree();
/* Let us create following BST
50
/
30 70
/ /
20 40 60 80 */
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
System.out.println("Inorder traversal of the given tree");
tree.inorder();
System.out.println(" Delete 20");
tree.deleteKey(20);
System.out.println("Inorder traversal of the modified tree");
tree.inorder();
System.out.println(" Delete 30");
tree.deleteKey(30);
System.out.println("Inorder traversal of the modified tree");
tree.inorder();
System.out.println(" Delete 50");
tree.deleteKey(50);
System.out.println("Inorder traversal of the modified tree");
tree.inorder();
}
}
Explanation / Answer
class BinarySearchTree
{
/* Class containing left and right child of current node and key value*/
class Node
{
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
// Root of BST
Node root;
// Constructor
BinarySearchTree()
{
root = null;
}
// This method mainly calls deleteRec() for deleting the record with the key
void deleteKey(int key)
{
root = deleteRec(root, key);
}
/* A recursive function to delete a key in BST */
Node deleteRec(Node root, int key)
{
/* Base Case: If the tree is empty */
if (root == null) return root;
/* Otherwise, recur down the tree */
if (key < root.key)
root.left = deleteRec(root.left, key); // if key is less than the root proceed to the left child
else if (key > root.key) // if key is less than the root proceed to the left child
root.right = deleteRec(root.right, key); //going to delete the key
// if key is same as root's key, then This is the node
// to be deleted
else
{
// node with only one child or no child
if (root.left == null) // root has no left child so just return the right child
return root.right;
else if (root.right == null)
return root.left; // root has no right child so just return the left child
// node with two children: Get the inorder successor (smallest
// in the right subtree)
root.key = minValue(root.right); // we need to get the minimum value from the right chils
// Delete the inorder successor
root.right = deleteRec(root.right, root.key); //Delete the minimum value node from the right child
}
return root; //return the updated root
}
int minValue(Node root)
{
int minv = root.key; // setting minv
while (root.left != null) // looping till we get to the end of the left child
{
minv = root.left.key;
root = root.left;
}
return minv;
}
// This method mainly calls insertRec()
void insert(int key)
{
root = insertRec(root, key); //inserting the key
}
/* A recursive function to insert a new key in BST */
Node insertRec(Node root, int key)
{
/* If the tree is empty, return a new node */
if (root == null) // if root is null just assign root to the new node.
{
root = new Node(key);
return root;
}
/* Otherwise, recur down the tree */
if (key < root.key)
root.left = insertRec(root.left, key); // if key is less than root key, move to the left child
else if (key > root.key)
root.right = insertRec(root.right, key); // if key is more than root key, move to the right child
/* return the (unchanged) node pointer */
return root;
}
// This method mainly calls InorderRec()
void inorder()
{
inorderRec(root); //This is inorder traversal
}
// A utility function to do inorder traversal of BST
void inorderRec(Node root)
{
if (root != null)
{
inorderRec(root.left); //Moving to left child
System.out.print(root.key + " "); //printing the node value
inorderRec(root.right); //Moving to right child
}
}
// Driver Program to test above functions
public static void main(String[] args)
{
BinarySearchTree tree = new BinarySearchTree();
/* Let us create following BST
50
/
30 70
/ /
20 40 60 80 */
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
System.out.println("Inorder traversal of the given tree");
tree.inorder();
System.out.println(" Delete 20");
tree.deleteKey(20);
System.out.println("Inorder traversal of the modified tree");
tree.inorder();
System.out.println(" Delete 30");
tree.deleteKey(30);
System.out.println("Inorder traversal of the modified tree");
tree.inorder();
System.out.println(" Delete 50");
tree.deleteKey(50);
System.out.println("Inorder traversal of the modified tree");
tree.inorder();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.