Lower Bound: Final

• A Binary Tree with k leaves must have height at least lg k.

• The height of the tree is the length of the longest path from root to leaf.

• A binary tree with n! leaves must have height at least lg n!

Previous slide

Next slide

Back to first slide

View graphic version