(step (step (step (step (step figure replace node with replace node delete leaf node with deleting node from the given binary search tree delete (treevalstep if tree null write "val not found in the treeelse if val data delete(tree->leftvalelse if val tree -data delete(tree -rightvalelse if tree -left and tree -right set temp findlargestnode(tree -leftset tree -data temp -data delete(tree -lefttemp -dataelse set temp tree if tree -left null and tree -right null set tree null else if tree -left !null set tree tree -left else set tree tree -right [end of iffree temp [end of ifstep end is called recursively on the node' right sub-tree note that if we have found the node whose value is equal to valthen we check which case of deletion it is if the node to be deleted has both left and right childrenthen we find the in-order predecessor of the node by calling findlargestnode(tree -leftand replace the current node' value with that of its in-order predecessor thenwe call delete(tree -lefttemp -datato delete the initial node of the in-order predecessor thuswe reduce the case of deletion into either case or case of deletion if the node to be deleted does not have any childthen we simply set the node to null last but not the leastif the node to be deleted has either left or right child but not boththen the current node is replaced by its child node and the initial child node is deleted from the tree the delete function requires time proportional to the height of the tree in the worst case it takes (log ntime to execute in the average case and (ntime in the worst case determining the height of binary search tree in order to determine the height of binary search treewe calculate the height of figure algorithm to delete node from binary search tree the left sub-tree and the right sub-tree whichever height is greater is added to it for exampleif the height of the left sub-tree is greater than that of the right sub-treethen is added to the left sub-treeelse is added to the right sub-tree look at fig since the height of the right sub-tree is greater than the height of the left sub-treethe height of the tree height (right sub-tree figure shows recursive algorithm that determines the height of binary search tree in step of the algorithmwe first check if the current node of the tree null if the condition is truethen is returned to the calling code otherwisefor every node we recursively call the algorithm to calculate the height of its left sub-tree as well as its right sub-tree the height of the tree at that node is given by adding to the height of the left sub-tree or the height of right sub-treewhichever is greater figure binary search tree with height determining the number of nodes determining the number of nodes in binary search tree is similar to determining its height to calculate the total number of elements/nodes