0

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?

user928112
  • 483
  • 1
  • 6
  • 24

2 Answers2

2

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.

k_ssb
  • 6,024
  • 23
  • 47
  • Thanks, that makes sense. In the previously answered question (linked in my original post), what is the purpose of the theorem? According to that same post, establishing that n <= 2^h is just a lemma, which I'm assuming means that it doesn't prove the original statement by itself. Would it not be enough to prove n <= 2^h and then take a log of both sides to show its relationship to the tree's height? – user928112 May 14 '18 at 06:31
  • @user928112 Not sure. I think my proof is just as valid as your linked proof but much more straightforward. – k_ssb May 14 '18 at 06:45
1

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.

Sekuraz
  • 548
  • 3
  • 15