Binary search tree deletion

to delete a particular node in a binary search tree there are three cases

• case1: deleting a node that has no children
• case2: deleting a node that has only one child
• case3: deleting a node that has only two child nodes

point 1:to delete a node compare given node with the root node whether it is greater or lesser than the root node.

point 2:if the given key node is greater than traverse on the right subtree

point 3:if the given key node is lesser than traverse on the left subtree

point 4: this is done recursively for each node until the (key node)deleted node is found,otherwise, node doesn’t exist

deleting a node that has no children

a node that doesn’t have any children is also called a terminal node or leaf node, these types of nodes can be easily deleted, without any issues because there are no child nodes

let’s look into one example given below, delete node 39 from below binary search tree, use points 1,2,3,4 from above to traverse

step1: searching starts from the root node 35,the given key node 39 which is greater than the root node 35,so traverse should be done on right sub tree

step 2:root node is 43, given key node to delete is 39 which is lesser than the 43, so traverse on the left subtree

step 3:key node is matched to the present root node (leaf node) 39, so this node will be deleted easily because there is no sub-nodes to it

step 4:binary search tree after deleting a given key node

deleting a node that has only one child

to delete a node that has one child node, the node to be deleted(key node) has a one child node, the node to be deleted is the parent node for one child node, use that child node replace the parent node with its child node

let’s look into one example given below, delete node 53 from below binary search tree, use points 1,2,3,4 from above to traverse

step1: search starts from the root node 49, the given key node 53 which is greater than the root node 35,so traverse should be done on the right subtree

step 2:root node is 56, given key node to delete is 53 which is lesser than the 56, so traverse on the left subtree

step 3:root node is matched to the key node(53==53), so replace this node with its child node 66

step 4:node 66 is replaced with its parent node 53

deleting a node that has only two child nodes