BST Deletion Flashcards
What is the first step when deleting in a BST?
After you have searched for the item to be deleted, what are the 3 possibiities?
Once you’ve found the item, there are three possibilities: It’s in:
- A Leaf
- A one-child node
- A two-child node
How do you delete a leaf in a BST?
To delete a leaf: simply set the parent’s child pointer to null (it’s a linkedlist after all)
How do you delete a node with only one child?
What would the attached tree look like if we deleted 19?
Simply replace the node with it’s child
What is the definition of an inorder successor?
In general what do you need to do to delete a node n with two children?
What is the code for deletion implementation for easy cases?
What do you need to watch out for in implementing code for deletion of easy case?
What is code for the helpe-method that deletes a node with two children(not an easy case)?
What is the code to implement delete iteratively in a BST (with the two helper cases)?
