In a full binary tree of depth $d$, what is the number of pairs of vertices at distance $t$ from each other?

Question

I can come up with a dynamic-programming-type program to compute this number, but I am wondering if a nice closed form formula is known.

By "full" I mean a binary tree where every vertex is within distance $d$ of the root, and the $d$-th level is completely filled with leaves. There are $2^{d+1} - 1$ total nodes.

Answer 1

Here's an attempt. This turned out to be quite messy though.

If $d$ is the depth of the tree and $t$ is even and smaller than $d$, the number of pairs $f(d)$ at distance $d$ is, I believe:

$$f(d) = \frac{1}{4} ( (t+3)2^d+3 \cdot 2^d 2^{t/2}- (t + 3)2^t )$$

Let's take a breath and see why. Of course any confirmation/opposition will be welcome.

Call $r$ the root of the tree $T$. Denote by $R(d)$ the number of nodes at distance $t$ from $r$, and by $C(d)$ the number of pairs at distance $t$ that have $r$ on their shortest path (i.e. the path crosses through $r$ but does not end in $r$.

Then

$$f(d) = 2f(d - 1) + R(d) + C(d)$$

When $d \geq t$, it is straightforward to show that $R(d) = 2^t$.

As for $C(d)$, for a vertex at depth $i$ in the "left" subtree, all vertices at depth $t - i$ in the "right" subtree are at distance $t$. There are $2^{i - 1}$ such choices left, and $2^{t - i - 1}$ choices right, and $C(d)$ is given by

$$\sum_{i = 1}^{t - 1}2^{i - 1}2^{t - i - 1} = (t - 1)2^{t - 2}$$

So $$f(d) = 2f(d - 1) + 2^t + (t - 1)2^{t - 2}$$

If we knew $f(t)$ we could solve the recurrence. It turns out that $f(t) = \frac{3}{4}(2^{3t/2})$. Plugging stuff into Wolfram, we get the closed form from above.

Now you may ask "why is $f(t) = \frac{3}{4}(2^{3t/2})$" ? I'll leave that as an exercise :)

But here's the idea. If $d < t/2, f(d) = 0$.
Recalling that $t$ is even, you can check that $f(t/2) = C(t/2) = 2^{t - 2}$ and for $\delta < t/2$,

$$f(t/2 + \delta) = 2f(t/2 + \delta - 1) + C(t/2 + \delta) =2f(t/2 + \delta - 1) + (2\delta + 1)2^{t - 2}$$

the idea for $C(t/2 + \delta)$ being to apply the same summation as above, but restricted to the allowable $i$'s given $d$.

From this, you can find $f(t - 1)$ using wolfram, and compute $f(t) = 2f(t - 1) + 2^t + (t - 1)2^{t - 2}$. This gives $\frac{3}{4}(2^{3t/2})$. The beauty of this expression hints that it should be right :) The non beauty of $f(d)$ in general leaves doubt though.

And for odd $t$, I guess you could apply the same ideas. I think only the $C(d)$ for $d < t$ will change.

Answer 2

Observe that each interior vertex (other than the root) of a binary tree is the central vertex of three different paths of length two, whereas the root is the central vertex of one such path. Furthermore, there are exactly $2^d-2$ interior vertices (other than the root) in a full binary tree. Writing $p(d,2)$ for the number of paths of length two in a full binary tree of depth $d$:

$$p(d,2)=3(2^d-2)+1=3\cdot 2^d-5.$$

Using a similar direct counting approach for $t=2k$, I have found the following formulae for $p(d,2k)$, the number of pairs of vertices at distance exactly $2k$ in a full binary tree of depth $d$.

• if $d<k$, then $p(d,2k)=0$
• if $k\le d<2k$, then $p(d,2k)=2^{2k-2}\left(3\cdot 2^{d-k+1}-2(d-k)-5\right)$
• if $d\ge 2k$, then $p(d,2k)=2^{2k-2}\left(3\cdot 2^{d-k+1}-2k-3\right)$

These appear to give the correct counts for small values of $d$ and $k$. In particular, for $t=2$ ($k=1$) and $d> 1$, the expression above becomes

$$p(d,2)=2^{2-2}\left(3\cdot 2^{d-1+1}-2-3\right)=3\cdot 2^d-5.$$

If you have any exact counts for larger values of $t$, perhaps you could check the validity of these formulae.