Deletion in a Binary Search Tree (Implementation)
Explore how to implement the delete operation in a binary search tree using Python. Understand handling deletion cases like empty trees, leaf nodes, nodes with one child, and nodes with two children by finding the inorder successor. This lesson aids in mastering BST manipulations crucial for coding interviews.
Introduction
Let’s implement the delete function for BSTs. We’ll build upon the code as we cater for each case.
Also, note that the delete function in the BinarySearchTree class is simply calling the delete function in the Node class where the core of our implementation will reside.
1. Deleting an Empty Tree
Let’s start with a skeleton function definition and cater for the first case. If the root does ...