Lesson 088
BST Operations
Search · Insert · Delete
1:00How to search, insert, and delete in a binary search tree — including the three deletion cases and why balance determines whether BST operations run in O(log n) or O(n).
By the end, you can
- State the BST ordering invariant and verify whether a given tree satisfies it.
- Trace the search path for a hit or a miss in a BST.
- Explain why in-order traversal of a BST produces keys in sorted order.
- Identify which of the three deletion cases applies (leaf / one child / two children) for any target node.
- Execute the in-order successor technique for deleting a node with two children.
- Explain why the in-order successor always has at most one child and is therefore easy to remove.
- Analyze BST operation cost as O(h) and describe when h equals O(log n) versus O(n).
- Explain what degeneration is and why self-balancing trees exist.
Up next in Trees, Hashing & Graphs
