<p>The lower bound is $\Omega(\log n)$ paths with $O(\log n)$ branching nodes, if you have at least $\Omega(\log n)$ branching nodes in the tree.</p>

<p>This can be achieved: use a tree which has one long path (length $n$) all of whose nodes are branching nodes, with no other branching nodes in the tree.</p>

<p>Here is a sketch of the lower bound.</p>

<p>First, compactify the tree by contracting any interior node that isn't a branching node. If the original size of the tree was $&lt; n^c$, the new tree must still be $&lt; n^c$, since you've only reduced the number of nodes. Now, the depth of a leaf is the number of branching nodes on the original path to that leaf, and we have a complete binary tree (every node has either degree 2 or 0). </p>

<p>If there are no leaves of depth $\Omega(\log n)$, then the number of paths is one more than the number of branching nodes, which is $\Omega(\log n)$, so we can assume that at least one leaf has depth $\Omega(\log n)$. </p>

<p>Next, recall Kraft's inequality. If the depth of a leaf in a complete binary tree is $d(v)$, then $\Sigma_{v \mathrm{\ leaf}} 2^{-d(v)} = 1$. </p>

<p>Now, we have fewer than $n^c$ leaves. We want to show that we have a lot of them at depth $O(\log n)$. Suppose we eliminate from consideration the ones that are depth at least $\log_2(n^{c+1}) = (c+1) \log_2 n$. This removes at most weight $1/n$ from the sum in Kraft's inequality, so for those leaves $v$ at depth at most $d(v)\leq (c+1) \log_2 n$, we have $\sum_{v\mathrm{\ low \ depth \ leaf}} 2^{-d(v)} &gt; 1-\frac{1}{n}$.  We also have $\sum_{v\mathrm{\ low\ depth\ leaf}} 2^{-d(v)} &lt; 1$ (since at least one leaf has depth too large to be included in this sum). </p>

<p>It's fairly easy to show that to get a sum of numbers $2^{-k}$ strictly between $1$ and $1-\frac{1}{n}$, we need at least $\log_2 n$ of them. This shows that there are $\Omega(\log n)$ paths with $O(\log n)$ branching nodes.</p>

CC BY-SA 2.5
2010-12-14T23:33:41.500Z
If anybody is wondering why I'm calling an equation an inequality, Kraft's inequality has an equal sign for *complete* binary trees.
Peter Shor 
CC BY-SA 2.5
2010-12-15T00:09:03.963Z
Thank you for this nice answer. I didn't know Kraft's inequality up to now. Very useful inequality.
Marc Bury
CC BY-SA 2.5
2010-12-14T22:56:18.890Z
2010-12-14T23:03:40.020Z
2010-12-14T23:03:40.020Z
Peter Shor 
<p>Let $T$ be a rooted binary tree. Every path from the root of $T$ to a leaf has length $n$. Every node of $T$ has always a left and a right child node but it is possible that they are the same (So there are always $2^n$ paths possible). The size of $T$ is bounded by $O(poly(n))$. A node with different child nodes is called <em>branching node</em>.</p>

<p>We say that two paths are different iff there is one shared branching node and one path goes to the left child node and the other path goes to the right child node.
It is clear that there is at least one path in $T$ with $O(\log n)$ branching nodes. Otherwise there would be too much nodes in $T$. </p>

<p>Is there a better lower bound on the number of paths with $O(\log n)$ branching nodes if I know there are $\omega(\log n)$ branching nodes in the tree?</p>

CC BY-SA 2.5
2010-12-14T19:46:46.220Z
@Marc: The letter $T$ (5th line) is obviously from ``too much nodes in" (7th line)?
Oleksandr Bondarenko
CC BY-SA 2.5
2010-12-14T19:58:25.403Z
@Marc: Could you, please, make more precise your statement "two paths are different iff they use different child nodes in a branching node". You mean they're different if there is such a branching node where they use different child nodes?
Oleksandr Bondarenko
CC BY-SA 2.5
2010-12-14T20:07:48.950Z
I edit the question and try to make it more precise.
Marc Bury
CC BY-SA 2.5
2010-12-14T20:14:00.230Z
What about the tree that has just one path (and $n$ nodes)? Is that allowed?
Peter Shor 
CC BY-SA 2.5
2010-12-14T20:41:27.517Z
This is a good question. It is allowed but this is not the interesting case :) Then we should make a lower bound on the number of branching nodes in the tree, e.g. $\omega(\log n)$ branching nodes.
Marc Bury
CC BY-SA 2.5
2010-12-14T21:20:30.483Z
+1: I saw your comment about the motivation, thanks. (I removed my comment after reading Peter's.)
Kaveh
CC BY-SA 2.5
2010-12-14T21:31:15.813Z
@Marc: By the size of $T$ you mean the number of internal nodes or something else?
Oleksandr Bondarenko
CC BY-SA 2.5
2010-12-14T21:37:07.670Z
The size of $T$ is the number of nodes, i.e. internal + leaf nodes.
Marc Bury
<graph-theory><tree>
Lower bound on the number of "short" paths in a rooted tree with polynomial size
Marc Bury
# Lower bound on the number of "short" paths in a rooted tree with polynomial size

(Asked by: username_0 on 2010-12-14)

Let $T$ be a rooted binary tree. Every path from the root of $T$ to a leaf has length $n$. Every node of $T$ has always a left and a right child node but it is possible that they are the same (So there are always $2^n$ paths possible). The size of $T$ is bounded by $O(poly(n))$. A node with different child nodes is called *branching node*.

We say that two paths are different iff there is one shared branching node and one path goes to the left child node and the other path goes to the right child node.
It is clear that there is at least one path in $T$ with $O(\log n)$ branching nodes. Otherwise there would be too much nodes in $T$.

Is there a better lower bound on the number of paths with $O(\log n)$ branching nodes if I know there are $\omega(\log n)$ branching nodes in the tree?

**Tags:** graph-theory, tree

> **Comments:**
> **username_1**: @Marc: The letter $T$ (5th line) is obviously from ``too much nodes in" (7th line)?  
> **username_1**: @Marc: Could you, please, make more precise your statement "two paths are different iff they use different child nodes in a branching node". You mean they're different if there is such a branching node where they use different child nodes?  
> **username_0**: I edit the question and try to make it more precise.  
> **username_2**: What about the tree that has just one path (and $n$ nodes)? Is that allowed?  
> **username_0**: This is a good question. It is allowed but this is not the interesting case :) Then we should make a lower bound on the number of branching nodes in the tree, e.g. $\omega(\log n)$ branching nodes.  
> **username_3**: +1: I saw your comment about the motivation, thanks. (I removed my comment after reading Peter's.)  
> **username_1**: @Marc: By the size of $T$ you mean the number of internal nodes or something else?  
> **username_0**: The size of $T$ is the number of nodes, i.e. internal + leaf nodes.  

---

## 1 answers

### Answer by username_2 on 2010-12-14. Score: 9 | Accepted answer

The lower bound is $\Omega(\log n)$ paths with $O(\log n)$ branching nodes, if you have at least $\Omega(\log n)$ branching nodes in the tree.

This can be achieved: use a tree which has one long path (length $n$) all of whose nodes are branching nodes, with no other branching nodes in the tree.

Here is a sketch of the lower bound.

First, compactify the tree by contracting any interior node that isn't a branching node. If the original size of the tree was $< n^c$, the new tree must still be $< n^c$, since you've only reduced the number of nodes. Now, the depth of a leaf is the number of branching nodes on the original path to that leaf, and we have a complete binary tree (every node has either degree 2 or 0).

If there are no leaves of depth $\Omega(\log n)$, then the number of paths is one more than the number of branching nodes, which is $\Omega(\log n)$, so we can assume that at least one leaf has depth $\Omega(\log n)$.

Next, recall Kraft's inequality. If the depth of a leaf in a complete binary tree is $d(v)$, then $\Sigma\_{v \mathrm{\ leaf}} 2^{-d(v)} = 1$.

Now, we have fewer than $n^c$ leaves. We want to show that we have a lot of them at depth $O(\log n)$. Suppose we eliminate from consideration the ones that are depth at least $\log\_2(n^{c+1}) = (c+1) \log\_2 n$. This removes at most weight $1/n$ from the sum in Kraft's inequality, so for those leaves $v$ at depth at most $d(v)\leq (c+1) \log\_2 n$, we have $\sum\_{v\mathrm{\ low \ depth \ leaf}} 2^{-d(v)} > 1-\frac{1}{n}$. We also have $\sum\_{v\mathrm{\ low\ depth\ leaf}} 2^{-d(v)} < 1$ (since at least one leaf has depth too large to be included in this sum).

It's fairly easy to show that to get a sum of numbers $2^{-k}$ strictly between $1$ and $1-\frac{1}{n}$, we need at least $\log\_2 n$ of them. This shows that there are $\Omega(\log n)$ paths with $O(\log n)$ branching nodes.

> **Comments:**
> **username_2**: If anybody is wondering why I'm calling an equation an inequality, Kraft's inequality has an equal sign for *complete* binary trees.  
> **username_0**: Thank you for this nice answer. I didn't know Kraft's inequality up to now. Very useful inequality.  

---

