Lower bound on the number of "short" paths in a rooted tree with polynomial size

Question

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?

Answer 1

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.