Deleting From A Binary Search Tree

Last updated Jan 1, 2022 Edit Source

• Cs algorithms
• Cs data structures
• Cs trees

Deleting from a binary search tree can be a tricky process since we want to sustain the BST property of the tree upon deletion. We can split the deletion of a node into three cases depending on how many children that node has.

Just remove the node.

Replace the node with its child.

In this case, you have two choices:

• Replace the node we want to delete with the maximum node in the left subtree
• Replace it with the minimum node in the right subtree.

All these operations can be done in $O(log(n))$ time.