Depth-Balanced Binary Trees

Description of the problem

A directed graph $(V,E)$ is called a rooted binary tree if every vertex $v\in V$ (except the root) has in degree 1, and out-degree 0 (leaves) or out-degree 2 (internal vertices). Root has in-degree 0 and out-degree 2.

Now, let us define a recursive function $C\colon V\to \mathbb{N}$ as follows: if $v$ is a leaf then $C(v)=1$, if $v$ is an internal vertex then $C(v) = C(v_l) + C(v_r)$ where $(v,v_l)$ and $(v,v_r)$ are the directed edges coming out of $v$. Notice that $C(v)$ counts the number of leaves under the vertex $v$.

We define a binary tree as balanced if the difference between $C(v_l)$ and $C(v_r)$ is at most 1 for every internal vertex (including the root) $v\in V$.

Luckily, up to a graph isomorphism, there is only one balanced rooted binary tree on $n$ leaves.

Proof

Let $T_n$ be the number of balanced rooted binary trees on $n$ leaves. We will prove the assertion using strong induction on $n$.

It is easy to see that $T_n=1$. If $n=2k$ is even, then when we split the root $R$ into its children $R_l$ and $R_r$, the fact that the tree is balanced forces $C(R_l)=C(R_r)=k$. Then $T_{2k}=T_k^2=1$. If $n=2k+1$ is odd then, up to isomorphism, we can safely assume $C(R_l)=k+1$ and $C(R_r)=k$. Then $T_{2k+1}=T_{k+1}T_k=1$.

A Slight Modification

Now that we establish that there aren’t enough balanced graphs, let us modify the problem a bit. Let us define recursively \[ D(v) = \max( D(v_l), D(v_r) ) + 1 \] where $D(v)=0$ for any leaf $v\in V$. Notice this time $D$ calculate the depth of a tree.

This time we will call a binary tree depth-balanced if the difference between $D(v_l)$ and $D(v_r)$ is at most 1. This time we are going to count the number of isomorphism classes of depth-balanced binary trees.

Let $T_{n,d}$ be the number of depth-balanced binary trees on $n$ leaves of depth $d$. The easy cases are $T_{n,d} = 0$ when $n>2^d$ and $n\leq 2^{d-1}$. Then we have the following recurrence relation: \[ T_{n,d} = T_{n-2^{d-2},d-1} + \sum_{a\geq b,\ \ a+b=n} T_{a,d-1} T_{b,d-1} \] for $n\geq 2$.

An Implementation

(defun count-dbts (n d)
   (cond ((= n (expt 2 d)) 1)
         ((or (> n (expt 2 d)) (<= n (expt 2 (1- d)))) 0)
         (t (+ (count-dbts (- n (expt 2 (- d 2))) (1- d))
               (loop for i from 1 to (floor n 2) sum (* (count-dbts (- n i) (1- d)) 
                                                        (count-dbts i (1- d))))))))

COUNT-DBTS

Let us test:

(format nil "~{~{~a ~}~%~}"
   (loop for i from 1 to 7 collect
      (loop for j from (1+ (expt 2 (1- i))) to (expt 2 i) collect
            (count-dbts j i))))

1 
1 1 
1 2 1 1 
1 3 3 6 3 3 1 1 
1 4 6 18 18 33 31 56 31 33 18 18 6 4 1 1 
1 5 10 40 60 159 244 651 733 1392 1663 3009 2883 4151 3814 5888 3814 4151 2883 3009 1663 1392 733 651 244 159 60 40 10 5 1 1 
1 6 15 75 150 519 1103 3890 6594 17780 32530 84923 135303 301414 477901 1103408 1447390 2742249 3782146 7008110 8583033 14078255 16990708 28164391 29422747 42187120 44583409 62836982 58994758 73886109 67957444 89566178 67957444 73886109 58994758 62836982 44583409 42187120 29422747 28164391 16990708 14078255 8583033 7008110 3782146 2742249 1447390 1103408 477901 301414 135303 84923 32530 17780 6594 3890 1103 519 150 75 15 6 1 1