# 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#

Last updated on by vishal devxo