Deletion in a Binary Search Tree
Explore how to delete nodes in a Binary Search Tree in Python by understanding six distinct cases: deleting an empty tree, leaf nodes, nodes with one child, and nodes with two children. Learn to handle each scenario with clear examples and visual strategies.
Introduction
We are going to study how a node is deleted in a BST. In general, to delete a node in a BST, you will search for it and, once found, you’ll make it None by making the left or right child of its parent None. However, to make things simpler, we’ve identified six possible cases involved in BST node deletion. We’ll tackle each one separately.
- Deleting in an empty tree
- Deleting a node with no children, i.e., a leaf node.
- Deleting a node which has one