How to delete a node with 2 children nodes in a binary search tree?
Solution 1
you replace said node with the left most child on its right side, or the right most child on its left side. You then delete the child from the bottom that it was replaced with.
Deleting five could yield either a tree with 3 as its root or 18 as its root, depending on which direction you take.
It looks like you got that image from this site: http://www.algolist.net/Data_structures/Binary_search_tree/Removal
It shows the algorithm you want with images too.
Solution 2
For deleting a Node there are three scenarios possible..
- Node is a leaf node: This is a simple case, figure out whether this node is left or right node of parent and set null as child for the parent for that side.
- Node is having one child: Establish a direct link between parent node and child node of this node.
- Node has two children: This is little tricky.. the steps involved in this are.
- First find the successor (or predecessor) of the this node.
- Delete the successor (or predecessor) from the tree.
- Replace the node to be deleted with the successor (or predecessor)
Before knowing the concept of deletion, we should understand the concept of successor and predecessors
Successor: In a binary tree successor of a node is the smallest node of the tree that is strictly greater then this node.
There are two possible cases with a node
A node has right children: In this case the leftmost child of the right sub-tree will be successor.
-
A node has no children: Go to the parent node and find a node for which this node is part of left sub-tree.
public Node sucessor(Node node) { Node sucessor = null; if (node.getRightNode() != null) { Node newNode = node.getRightNode(); while (newNode != null) { sucessor = newNode; newNode = newNode.getLeftNode(); } } else { sucessor = findRightParent(node); } return sucessor; } private Node findRightParent(Node node) { Node newNode = null; if (node.getParentNode() != null) { if (node.getParentNode().getLeftNode() == node) { newNode = node.getParentNode(); } else { newNode = findRightParent(node.getParentNode()); } } return newNode; }
Now the deletion logic
public void deleteNode(Node node) {
// Node is a leaf node //
if( node.getLeftNode() == null && node.getRightNode() == null){
if(isRightNode(node.getParentNode(), node)){
node.getParentNode().setRightNode(null);
}else{
node.getParentNode().setLeftNode(null);
}
// Only left child is there//
}else if( node.getLeftNode() != null && node.getRightNode() == null){
if(isRightNode(node.getParentNode(), node)){
node.getParentNode().setRightNode(node.getLeftNode());
}else{
node.getParentNode().setLeftNode(node.getLeftNode());
}
// Only Right child is there //
}else if( node.getLeftNode() == null && node.getRightNode() != null){
if( isRightNode(node.getParentNode(), node)){
node.getParentNode().setRightNode(node.getRightNode());
}else{
node.getParentNode().setLeftNode(node.getRightNode());
}
// Both Left and Right children are their//
}else{
Node psNode = predessor(node);
deleteNode(psNode);
psNode.setParentNode(node.getParentNode());
psNode.setLeftNode(node.getLeftNode());
psNode.setRightNode(node.getRightNode());
if( isRightNode(node.getParentNode(), node)){
node.getParentNode().setRightNode(psNode);
}else{
node.getParentNode().setLeftNode(psNode);
}
}
}
Solution is taken from http://coder2design.com/binary-tree/
Also they have explained the flow of traversal and insertion with full source code.
Solution 3
A simple and easy solution:
Node* findMaxNode(Node* root)
{
if(root->right == NULL) return root;
findMaxNode(root->right);
}
Node* DeleteNodeInBST(Node* root,int data)
{
//base case when not found or found then recursion breaks
if(root == NULL) return root;
else if(root->data > data) root->left = DeleteNodeInBST(root->left, data);
else if(root->data < data) root->right = DeleteNodeInBST(root->right, data);
else
{
//when the node to be deleted is found
//Four possibilities
//case1: When the node to be deleted has no children
if(root->left == NULL && root->right == NULL)
{
delete root;
root = NULL;
}
//case2: When the node to be deleted has ONLY LEFT child
else if(root->right == NULL)
{
Node* temp = root;
root = root->left;
delete temp;
}
//case3: When the node to be deleted has ONLY RIGHT child
else if(root->left == NULL)
{
Node* temp = root;
root = root->right;
delete temp;
}
//case4: When the node to be deleted has TWO children
else
{
Node* maxNode = findMaxNode(root->left);//finding the maximum in LEFT sub-tree
root->data = maxNode->data; //Overwriting the root node with MAX-LEFT
root->left = DeleteNodeInBST(root->left, maxNode->data);//deleted the MAX-LEFT node
}
return root;
}
}
Solution 4
Wikipedia article gives a good description of BST:
http://en.wikipedia.org/wiki/Binary_search_tree
When you delete a node with 2 children, 5 in your case, you can replace the deleted node with minimum value node from the right subtree, or maximum value node from the left subtree.
Related videos on Youtube
18 : 27
10 : 27
05 : 07
03 : 07
05 : 16
Dinesh
The more I learn, the more I realize how much I don't know. #SOreadytohelp
Updated on January 11, 2020Comments
-
Dinesh over 4 years
How to delete a node with 2 children nodes in a binary tree?
Is there any kind of method to remove it? I googled it. But didn't get clear idea about it. Anybody explain it with diagrammatic representation?
How to delete the node '5' from the this image and what might be the outcome?
-
Rupinder Ghotra about 9 yearsThis program works but uses a different approach. Can someone tell, why I had been down voted?
-
Lampros Tzanetos about 6 yearsCan I either delete the left most child on its right side, or the right most child on its left side? Doesn't it make any difference?
-
Lampros Tzanetos about 6 yearsCan I either delete the left most child on its right side, or the right most child on its left side? Doesn't it make any difference?
