Core · Module 10 · Lesson 3 of 5
Insert and delete
Inserting into a binary search tree is a search that ends by attaching a node. Deleting is harder when the node has two children: its successor takes its place.
By the end you can
- Insert a key by searching for its empty spot, using the return-the-subtree pattern
- Delete a node with zero, one or two children while keeping the search tree property
- Explain how the order of insertions and deletions shapes the tree
Builds on Binary search trees.
01 · A question first
Deleting a leaf from a binary search tree is one pointer write. Deleting the root, which has two children, can't simply remove the node: two subtrees would be left with no parent. Which key takes its place, and why does that one keep every rule intact?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- Insertion is a search
- Deleting a node
- Cost and shape
- Iterative versions
- Duplicates
- Checking your tree
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
- Complexity Derivation, Edge Cases & Common Mistakes
03 · Practice
Asked in interviews
Something wrong with this lesson? Report a problem