DSA TrainerFoundations · Unit 10
Trees and Binary Search Trees
You have seen two ways to store a collection. A sorted array gives you fast search (binary search, O(log n)) but slow insertion, because adding an element shifts everything after it. A linked list gives you fast insertion but slow search, because you have to walk the chain. Each is good at one thing and bad at the other.
A binary search tree tries to give you both. Instead of a line, it organizes values in a branching structure where every step down the tree rules out a chunk of the data, the same halving idea behind binary search, but on a structure you can also insert into cheaply.
The catch, which we will get to, is that a tree only delivers that speed when it stays balanced. This unit builds up the binary tree, the ordering rule that makes it searchable, what you get from walking it, and the balance problem that decides whether it is fast or slow.
You’re not signed in. Your progress here won’t be saved.
The tree: nodes and children
A tree is nodes connected in a hierarchy, like an org chart. The top node is the root. Each node can have children below it, and a node with no children is a leaf. Every node except the root has exactly one parent.
A binary tree is the common special case where each node has at most two children, usually called left and right. So from any node you can go down to its left child, its right child, both, or neither. That simple "at most two children" shape is the foundation everything else here builds on.
In a binary tree, what is a leaf?
The drills and graded test are premium
The lessons above are free. The interactive practice that turns recognizing the pattern into recalling it on a blank page unlocks with premium:
- ✓2 applied drills: train spotting when the concept applies
- ✓A 5-question graded test to clear the unit
- ✓The full guided problem ladder with faded hints, plus the cold-read capstone
From $6/month. Cancel anytime.