Core Concept Mastery • DSA Module
Tree operation complexity depends on tree height. Balanced trees have height O(log n), giving O(log n) operations. Skewed trees have height O(n), degrading to O(n) operations. Traversal always visits all nodes, so it's O(n) regardless of shape.
Searching in a phone book: If names are randomly distributed (balanced BST), you find any name in ~20 steps (log₂ of 1 million). If names are in alphabetical order and inserted sequentially (skewed BST), you might need to check all 1 million names (worst case).
| Operation | Average (Balanced) | Worst (Skewed) |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Traversal | O(n) | O(n) |
Complexity depends on height, not number of nodes. Balanced = O(log n), Skewed = O(n).
Why Worst Case? See below:
Height = n
Search = O(n)
Height = log n
Search = O(log n)
For 1 million elements:
~20 comparisons
Up to 1M comparisons
50,000x difference!
Why Height Matters
The Key Insight
Tree operations depend on height, not number of nodes:
Balanced Tree (Best Case)
Skewed Tree (Worst Case)
Why Traversal is Always O(n)
Traversal visits every node exactly once, regardless of tree shape:
Average vs Worst Case
Real-World Impact
For n = 1,000,000:
This is why self-balancing BSTs (AVL trees, Red-Black trees) automatically maintain balance, guaranteeing O(log n) operations even with worst-case insertions.
Understanding complexity helps you choose the right data structure and predict performance. A balanced BST gives O(log n) search — excellent for large datasets. A skewed BST gives O(n) search — no better than a linked list. This is why balanced BSTs (AVL, Red-Black) exist.
"Why does a skewed Binary Search Tree have O(n) search time complexity?"
A skewed BST degenerates into a linked list with height = n. When searching, you must traverse from root to leaf, following a path of length n. Since you can't eliminate half the tree at each step (there's only one path), you must check up to n nodes, giving O(n) worst-case complexity.