# Lower bound on the number of “short” paths in a rooted tree with polynomial size

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?

• @Marc: The letter $T$ (5th line) is obviously from too much nodes in" (7th line)? – Oleksandr Bondarenko Dec 14 '10 at 19:46
• @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 Dec 14 '10 at 19:58
• I edit the question and try to make it more precise. – Marc Bury Dec 14 '10 at 20:07
• What about the tree that has just one path (and $n$ nodes)? Is that allowed? – Peter Shor Dec 14 '10 at 20:14
• 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 Dec 14 '10 at 20:41

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.

• 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 Dec 14 '10 at 23:33
• Thank you for this nice answer. I didn't know Kraft's inequality up to now. Very useful inequality. – Marc Bury Dec 15 '10 at 0:09