Binary Tree – Deleting a Node
The possibilities which may arise during deleting a node from a binary tree are as follows:
- Node is a terminal node: In this case, if the node is a left child of its parent, then the left pointer of its parent is set to NULL. Otherwise if the node is a right child of its parent, then the right pointer of its parent is set to NULL
- Node has only one child: In this case, the appropriate pointer of its parent is set to child node.
- Node has two children: Predecessor replaces the node value, and then the predecessor of the node is deleted.
Since the node has both, right and left child, if right sub-tree is opted find the smallest node. If left sub-tree is opted then find the largest node.
Since node->right = node->left = NULL, delete the node and place NULL in the parent node.
Node Removal Operation
If the node to be removed is a leaf node, it can be deleted immediately. If the node has one child, the node can be deleted after its parent adjusts a link to bypass the deleted node.
What if the node numbered 2 is deleted?
t à right
set t = t à right
If the node to be removed has two children, the general strategy is to replace the data of this node with the smallest data of the right sub-tree. Then the node with the smallest data is now removed (this case is easy since this node cannot have two children).
Remove the numbered 2 again.