[go: up one dir, main page]
Scribd
Upload
44 views2 pages

Binary Search Tree (BST) - Deletion Algorithm

The document outlines the steps and algorithms for deleting a node from a Binary Search Tree (BST) and a binary tree. For a BST, it involves checking the node's position relative to the root and handling various cases based on the node's children. In a binary tree, the deletion process involves replacing the target node with the deepest rightmost node and then removing that node.

Uploaded by

shabilmohamed1234
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
44 views2 pages

Binary Search Tree (BST) - Deletion Algorithm

The document outlines the steps and algorithms for deleting a node from a Binary Search Tree (BST) and a binary tree. For a BST, it involves checking the node's position relative to the root and handling various cases based on the node's children. In a binary tree, the deletion process involves replacing the target node with the deepest rightmost node and then removing that node.

Uploaded by

shabilmohamed1234
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Delete a node from Binary Search Tree(BST)

Main steps to solve the problem:

1. If the root is NULL, then return root (Base case)


2. If the key is less than the root’s value, then set root->left = deleteNode(root->left, key)
3. If the key is greater than the root’s value, then set root->right = deleteNode(root->right,
key)
4. Else Check
4.1 If the root is a leaf node then return null
4.2 else if it has only the left child, then return the left child
4.2 else if it has only the right child, then return the right child
4.3 else set the value of root as of its inorder successor and recur to delete the node with
the value of the inorder successor
5. Return

Algorithm:

deleteNode(root, val)
Input: Root of the tree and value of the node to be deleted
Output: address of root node

1. if(root == NULL)
2. return NULL
3. if(root->key < val)
4. root->right = deleteNode(root->right,val)
5. else if(root->key > val)
6. root->left = deleteNode(root->left,val)
7. else
8. if(root->left == NULL && root->right == NULL)
9. free(root)
10. return NULL
11. else if(root->left == NULL)
12. temp = root->right;
13. free(root)
14. return temp
15. else if(root->right == NULL)
16. temp = root->left
17. free(root)
18. return temp
19. else
20. rightMin = find_InorderSuccessor(root->right)
21. root->key = rightMin
22. root->right = deleteNode(root->right,rightMin)
23. return root; //return the actual root's address

Deletion of a node in a binary tree


Since we do not have any ordering among the elements of a binary tree, we replace the
key of the node to be deleted with the key of the rightmost node in the deepest level and
free deepest rightmost node.

Algorithm:

1. Starting at the root, find the deepest and rightmost node in the binary tree and the node
which we want to delete.
2. Replace the deepest rightmost node’s data with the node to be deleted.
3. Then delete the deepest rightmost node.

You might also like