Every BST operation walks one path from the root, so its cost is the tree's height h — not its size. The same seven values can make a tree of height 3 or of height 7, depending only on the order they were inserted. Keeping h small is what "balanced" means, and it's the difference between O(log n) and O(n).
Members only · free account
The rest of this lesson, with 4 more sections, 2 drawings, a dry-run simulator and code in JavaScript, Python, Java and C++, opens with a free account.
Not ready yet? The Arrays course is free to read, no account needed.
In the rest of this lesson