What is the lower bound for the height of a binary search tree with n nodes?
Show answer
Omega(log n)
A perfectly balanced binary tree has a height of log2(n). While a BST can degenerate into a linear chain of O(n) height, balanced variants like AVL or Red-Black trees maintain the O(log n) bound.
Also asked as:
- What is the asymptotic lower bound for the height of any binary search tree containing n nodes?