CODEWITHSUNDEEP
binary-treeproof
user928112
user928112

Reputation: 582

Prove that a binary tree with n leaves has a height of at least log n

I know that the number of leaves in a binary tree of height h can be at most 2^h, and I also know how to prove this using induction. Where do I go from here?

I found this previously answered question, but this doesn't make any sense to me because I don't understand what the proof by contradiction in the theorem section has anything to do with a binary tree's height being at least log(n). I was expecting him to talk about how log(n) relates to the number of leaves and height, but instead he goes on to talk about how to do a proof by contradiction using n = 2^a + b.

Can anyone help me understand how we can prove that the height of a BT with n leaves will be at least log n?

Upvotes: 0

Views: 2092

Answers (2)

Sekuraz
Sekuraz

Reputation: 588

So you know that your binary tree has the following properties:

n <= 2^h

Now you can use a log on both sides because both are positive and that's it from a math point of view.

In order to understand it better you can do the following: If you have a tree which is not full you traded 2 possible leaves for one actual leaf (because there could be 2 children). So the maximum number of leaves for any given height is a full tree which has 2^h leaves or log (n) height.

Upvotes: 1

k_ssb
k_ssb

Reputation: 6252

Consider a binary tree, and let h be its height and n be the number of its leaves.

By your first sentence, n <= 2^h. Taking a log base 2 on both sides (which preserves the inequality because log is monotonic), we have log(n) <= h. That immediately gives you what you wanted: the height is at least log(n), where n is the number of leaves.

Upvotes: 2

Related Questions