0

For a homework assignment, I need to prove that a Binary Tree of $n$ nodes has a height of at least $log(k)$. I started out by testing some trees that were filled at every layer, and checking $log(n)$ against their height:

when $n = 3$ and $h = 1$, $\log(3) = 0.48 \leq h$

when $n = 7$ and $h = 2$, $\log(7) = 0.85 \leq h$

when $n = 15$ and $h = 3$, $\log(15) = 1.18 \leq h$

when $n = 31$ and $h = 4$, $\log(31) = 1.49 \leq h$

By this point, I realized that every layer, $n = n*2+1$ from the previous layer, and obviously the height increases by 1.

To try to follow the trajectory, I plotted it:Wolfram Alpha, and it looks like the 2 lines will never meet.

Unfortunately though, I don't think this actually proves anything.

Can someone point me in the right direction from here?

Zhanxiong
  • 14,040
Carcigenicate
  • 339
  • A good next step here would be to figure out the exact relation between $n$ and $h$ in the examples you found. You need to fix your notation because you are confusing yourself by using $n$ to mean different things. When you write $n = 2*n + 1$, the $n$ on the left means something different from the $n$ on the right. – Erick Wong Jul 09 '15 at 14:52
  • A suggestion would be to remove this confusion by studying the function $f(h)$ which is "how many nodes are there in a complete binary tree of height $h$?" Instead of writing $n = 2*n + 1$ you could then specify that $f(h) = 2 f(h-1) + 1$, since $f(h-1)$ allows you to express the concept of "$n$ from the previous layer". Note that you plotted $2n+1$ versus $\log n$: the fact that these graphs don't touch is completely irrelevant to the question (again, you're comparing functions of two different $n$s). – Erick Wong Jul 09 '15 at 14:55

3 Answers3

3

For each $k \in \{1, \ldots, h\}$, it is easily seen that the $k$th layer has $2^{k - 1}$ nodes, therefore, the total number of nodes is $$n = 1 + 2 + 2^2 + \cdots + 2^{h - 1} = \sum_{k = 1}^h 2^{k - 1} = 2^h - 1.$$

Solve this for $h$, we have for $n \geq 1$, $$h = \log_2(n + 1) > \log_2(n) > \log_{10}(n).$$

So in fact you can use the sharper lower bound $\log_2(n)$ instead of $\log_{10}(n)$.

Zhanxiong
  • 14,040
  • 1
    @Carcigenicate It's very likely that the homework question expects you to prove this with the $\log_2$ lower bound and not the $\log_{10}$ that you're assuming. – Erick Wong Jul 09 '15 at 14:57
  • @Eric The question uses "log n“. Since it doesn't specify a base, and there is an 'o' in there, I thought that that means base 10 log. – Carcigenicate Jul 09 '15 at 15:09
  • And unfortunately, I understand very little from this answer. The only postsecondary math course I've taken is an introduction into finite linear systems, which didn't cover anything you written above. – Carcigenicate Jul 09 '15 at 15:13
  • @Carcigenicate That's possible, it really depends on the conventions of your specific course, and you are certainly more qualified to know that than I am. A third possible interpretation would be natural log (base $e$). At least the statement is true for any of those bases :). – Erick Wong Jul 09 '15 at 15:16
  • @ErickWong This is the last question of the course, and the first time we've been asked to prove something (other than verify that code is working). And ya I understand that the assertion they're asking me to prove is true, I just don't see how I can prove that it's the case for every set of input. – Carcigenicate Jul 09 '15 at 15:21
  • This doesn't help me, but apparently it answers my question, so I'll accept it. For anyone else stuck in my position who isn't mathematically inclined, I ended up "proving it" via a program. I wrote up a recursive function that computes the total nodes at a given height, then in a loop, I'm checking if the height >= log(n). The instructor can run this to their heart's content to prove it. – Carcigenicate Jul 09 '15 at 16:40
1

Suppose we have a complete binary tree that has n nodes and h is its height (the maximum number of edges from the root to a leaf node).

In a complete binary tree, all levels except POSSIBLY the last are completely filled and all nodes are as left as possible (if a node has a child, that child must be a left child).

The level of a node is the number of edges from the root node to that node. So the root node has level 0. And all level-h nodes are leaf nodes. So the maximum level (h) is also the height (h) of the complete binary tree.

Level-0 has $2^0$ = 1 node

Level-1 has $2^1$ = 2 nodes

Level-2 has $2^2$ = 4 nodes …

Level-(h-1) has $2^{h-1}$ nodes

Level-h has a MAXIMUM of $2^h$ nodes

The MAXIMUM number of nodes this tree can have:

$$\sum_{k=0}^h 2^k=2^{h+1} - 1$$

The number of nodes of the sub-tree which contains all the levels from 0 to (h-1):

$$\sum_{k=0}^{h-1} 2^k=2^h - 1$$

The tree’s height is h, so $2^h - 1 + 1 \le n\le 2^{h+1} - 1$

Solve this inequality, we have $lg(n+1) - 1 \le h \le lg(n)$

or $h \in [lg(n+1) - 1, lg(n)]$

We have $lg(n) - (lg(n+1) - 1) = 1 - (lg(n+1) - lg(n)) < 1$

and with n > 0, we always have h which is a positive integer,

so there is only ONE integer $h \in [lg⁡(n+1)-1, lg⁡(n)]$.

So, h=FLOOR(lg⁡(n))

Complete binary tree has smallest height in the binary trees which have the same number of nodes.

Tuan Le PN
  • 111
0

Instead of plotting the number of nodes in the last level, you can plot the height of the tree vs lg n. I did it in the plot here. It basically proves that from x = 1 onwards (this is obvious because the binary tree is non-empty) the height of the tree is always greater than lg n which is the lower limit.

Oreo
  • 5