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