Show that the average depth of a leaf in a binary tree with n vertices is Omega(lgn)

Question

I'm showing like this. The depth of a tree would be at least lgn. Let C be the number of leaves. Therefore, Omega(lgn). Please tell me, Am I right ?

Answer 1

We start with the two functional equations

$$T(z) = z + z T^2(z)$$

and $$Q(z, u, v) = vz + z Q^2(z, u, uv)$$

where the first one is for binary trees and the second one for binary trees with the depth marked where we set the depth of the root to be zero. The variable $v$ marks leaves and $u$ counts the total depth. We need to extract coefficients from $T(z)$ for the probabilities. We will do this even though the answer is known, because we will re-use the computation later on.

We obtain

$$[z^n] T(z) = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} T(z) \; dz.$$

Using the functional equation we put $T(z) = w$ so that

$$z = \frac{w}{1+w^2} \quad\text{and}\quad dz = (1-w^2)/(1+w^2)^2 \; dw.$$

and we obtain

$$\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w^2)^{n+1}}{w^{n+1}} w \frac{1-w^2}{(1+w^2)^2} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w^2)^{n-1}}{w^{n}} (1-w^2)\; dw.$$

Extracting coefficients we get zero for $n$ even, one for $n=1$ and for $n$ odd, $n\ge 3,$

$${n-1\choose (n-1)/2} - {n-1\choose (n-3)/2} \\ = {n-1\choose (n-1)/2} - {n-1\choose (n-1)/2} \frac{(n-1)/2}{(n+1)/2} = \frac{1}{(n+1)/2} {n-1\choose (n-1)/2}.$$

Now for the average depth we require (yes the derivative is with respect to $u$)

$$A(z) = \left.\frac{\partial}{\partial u} Q(z,u,v)\right|_{u=1, v=1}.$$

Therefore we require

$$B(z) = \left.\frac{\partial}{\partial v} Q(z,u,v)\right|_{u=1, v=1}.$$

We have from the functional equation

$$B(z) = z + 2z T(z) B(z)$$ so that

$$B(z) = \frac{z}{1 - 2 z T(z)}.$$

Returning to $A(z)$ the functional equation yields

$$A(z) = 2z T(z) (A(z) + B(z))$$

or

$$A(z) = \frac{2z T(z) B(z)}{1 - 2 z T(z)} = \frac{2z^2 T(z)}{(1 - 2 z T(z))^2}.$$

The coefficient extraction integral becomes

$$[z^n] A(z) = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{2z^2 T(z)}{(1 - 2 z T(z))^2} \; dz.$$

Using the same substitution as before we obtain

$$\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w^2)^{n+1}}{w^{n+1}} \frac{2w^3/(1+w^2)^2}{(1 - 2 w^2/(1+w^2))^2} \frac{1-w^2}{(1+w^2)^2} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w^2)^{n-1}}{w^{n+1}} \frac{2w^3}{(1 - w^2)^2} (1-w^2) \; dw \\ = \frac{2}{2\pi i} \int_{|w|=\gamma} \frac{(1+w^2)^{n-1}}{w^{n-2}} \frac{1}{1 - w^2} \; dw.$$

This vanishes for $n=1$, is zero for $n$ even and for $n$ odd has the value

$$2\sum_{q=0}^{(n-3)/2} {n-1\choose q}.$$

Putting $n=2m+3$ we get

$$2\sum_{q=0}^{m} {2m+2\choose q} = 2\times \frac{1}{2} \times \left(2^{2m+2} - {2m+2\choose m+1}\right) = 2^{n-1} - {n-1\choose (n-1)/2}.$$

Recall that a binary tree on $n$ nodes with $n$ odd has $(n+1)/2$ leaves, as can be seen by a simple induction argument. This finally yields for the average depth

$$\frac{1}{(n+1)/2} \left(\frac{1}{(n+1)/2} {n-1\choose (n-1)/2}\right)^{-1} \times \left(2^{n-1} - {n-1\choose (n-1)/2}\right) \\ = {n-1\choose (n-1)/2}^{-1} \times \left(2^{n-1} - {n-1\choose (n-1)/2}\right) \\ = - 1 + 2^{n-1} \times {n-1\choose (n-1)/2}^{-1} .$$

We have from the asymptotic of the central binomial coefficient

$${n-1\choose (n-1)/2} = {2((n-1)/2)\choose (n-1)/2} \sim \frac{4^{(n-1)/2}}{\sqrt{\pi (n-1)/2}}$$

Therefore the average depth is

$$\bbox[5px,border:2px solid #00A000]{ -1+\sqrt{\pi (n-1)/2}.}$$

Remarks. The sequences for the total count (Catalan numbers) and the total depth can be found at OEIS A000108 and OEIS A068551. A Maple script to compute these from the functional equation goes like this:

CF :=
proc(k)
option remember;
    if k = 0 then return 0 end if;
    if k = 1 then return v end if;
    expand(subs(v = u*v, add(CF(q)*CF(k - 1 - q), q = 1 .. k - 1)))
end proc;


AVG := n-> subs([u=1, v=1], diff(CF(n), u))/
subs([u=1, v=1], CF(n))/((n+1)/2);

AVG2 := n -> -1 + sqrt(1/2 *Pi* (n - 1));

There is also a Perl script to compute them by total enumeration.

#! /usr/bin/perl -w
#

my @trees = (-1, [[]]);

sub btrees {
    my ($n) = @_;

    return $trees[$n] 
        if $n < scalar(@trees);

    my @res;

    for(my $k=1; $k<$n-1; $k++){
        foreach my $left (@{ btrees($k) }){
            foreach my $right (@{ btrees($n-1-$k) }){
                push @res, [$left, $right];
            }
        }
    }

    $trees[$n] = \@res;
    return $trees[$n];
}

sub treedepths {
    my ($tree, $tref, $depth) = @_;

    if(scalar(@$tree) == 0){
        $$tref += $depth;
        return;
    }

    treedepths($tree->[0], $tref, $depth+1);
    treedepths($tree->[1], $tref, $depth+1);
}

sub alldepths {
    my ($n) = @_;

    my $res = 0;
    foreach my $tree (@{ btrees($n) }){
        treedepths($tree, \$res, 0);
    }

    return $res;
}

 MAIN: {
     my $mx = int(shift || 7);

     for(my $n=1; $n <= $mx; $n++){
         my $count = scalar(@{ btrees($n) });
         my $depths = alldepths($n);

         print "$n: $count $depths\n";
     }

     1;
}

The result is a table that runs as follows:

1: 1 0
2: 0 0
3: 1 2
4: 0 0
5: 2 10
6: 0 0
7: 5 44
8: 0 0
9: 14 186
10: 0 0
11: 42 772
12: 0 0
13: 132 3172
14: 0 0
15: 429 12952

This can be extended to about $27$ nodes even though the script is not optimized.

This was also computed using a slightly different approach at the following MSE link.