Advanced · Module 20 · Lesson 1 of 5
Why binary search trees degrade
A binary search tree is only as fast as it is shallow, and its shape depends entirely on insertion order. Sorted input turns it into a linked list. Balanced trees fix the shape as they go.
By the end you can
- Explain why every binary search tree operation costs O(height), and how insertion order sets the height
- Recognize the inputs that make a plain tree degenerate, and the expected height under random order
- Rebuild a balanced tree from sorted data, and state what a self-balancing tree must guarantee
Builds on Insert and delete.
01 · A question first
A service stores user ids in a binary search tree. Ids are assigned in increasing order, so each new one is the largest so far. After a million sign-ups, a lookup takes a million steps instead of twenty. Nothing in the code is wrong. What happened to the tree?
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
- Speed comes from height
- Sorted input makes a chain
- Random order is fine, on average
- Rebuilding from sorted keys
- What a balanced tree must guarantee
- Where the tree shape matters
- 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