Counting binary trees

Why it exists

"How many different binary trees can be formed with $n$ nodes?" is one of the most repeated questions in the tree topic, in several disguises: unlabelled, labelled, search trees, full trees, trees of a given height, heaps. The answers are all built from the same recurrence, so once you can derive it you do not need to memorise a table. This page derives it once and then applies it.

Prerequisites

Precise definitions

A binary tree here is as defined on the trees page: every node has a left and a right child slot, each of which may be empty, and swapping the sides gives a different tree. Two trees are the same if they have the same shape (and, for labelled trees, the same label at each position).

The recurrence

Let $C_n$ be the number of binary trees with $n$ nodes (shapes only). The empty tree counts as one, so $C_0 = 1$. A tree with $n \ge 1$ nodes has a root, a left subtree with $i$ nodes and a right subtree with $n - 1 - i$ nodes, for some $i$ from $0$ to $n - 1$. The two subtrees are chosen independently, so

$C_n = \sum_{i=0}^{n-1} C_i \, C_{n-1-i}.$

This gives $C_0, C_1, C_2, \ldots = 1, 1, 2, 5, 14, 42, 132, 429, 1430, \ldots$ and the closed form

$C_n = \frac{1}{n+1}\binom{2n}{n}.$

This closed form is not derived on this page (the standard proof uses generating functions or a ballot-sequence argument; CLRS Problem 12-4 walks through one). Here it is checked against the recurrence by a program, and for GATE you only need to know it and the first values. These are the Catalan numbers. They grow like $4^n$ divided by a power of $n$, so they are exponential.

Variants

Trees of a given height

Let $A(n, h)$ be the number of binary trees with $n$ nodes and height at most $h$ (height of the empty tree $-1$). Then $A(0, h) = 1$ for $h \ge -1$, $A(n, -1) = 0$ for $n \ge 1$, and

$A(n, h) = \sum_{i=0}^{n-1} A(i, h-1)\, A(n-1-i, h-1).$

The number with height exactly $h$ is $A(n, h) - A(n, h-1)$. The extremes: the chain shapes number $2^{n-1}$ (each of the $n - 1$ non-root nodes is a left or a right child of the one above), and the smallest height is $\lceil \log_2(n+1) \rceil - 1$.

Counting orders, not shapes

• The number of insertion orders of $n$ distinct keys that build one particular binary search tree $T$ is $\frac{n!}{\prod_{v} s(v)},$ where $s(v)$ is the number of nodes in the subtree of $v$ (counting $v$). The reason: in any valid order every node must come before all the other nodes of its subtree, and the fraction of orders in which each node precedes the rest of its subtree is $1/s(v)$. (This is a sketch: it uses that these events are independent for different nodes. The formula itself was checked by brute force for $n \le 7$, and summing over all shapes does give $n!$.)
• The same formula counts the heaps: the number of ways to put the keys $1..n$ into the complete binary tree of $n$ nodes so that every parent is larger than its children is $n! / \prod_v s(v)$ over that complete tree.

How it works

Everything on this page is one idea: split on the root. Choose the size of the left subtree, count the ways for each side independently, multiply, and add over the choices of size. Labelled counts add one more factor (which labels go left: a binomial coefficient). The recurrences are run below.

Worked examples

#include <stdio.h>
 
int main(void) {
    long c[9] = {1};
    for (int n = 1; n <= 8; n++) {
        c[n] = 0;
        for (int i = 0; i < n; i++) c[n] += c[i] * c[n - 1 - i];
    }
    int ok = 1;
    for (int n = 0; n <= 8; n++) {
        long b = 1;
        for (int i = 1; i <= n; i++) b = b * (n + i) / i;
        ok = ok && b / (n + 1) == c[n];
    }
    long f[10] = {0};
    f[1] = 1;
    for (int n = 3; n <= 9; n += 2)
        for (int i = 1; i < n - 1; i += 2) f[n] += f[i] * f[n - 1 - i];
    for (int n = 0; n <= 8; n++) printf("%ld ", c[n]);
    printf("\n%d\n%ld %ld %ld %ld %ld\n", ok, f[1], f[3], f[5], f[7], f[9]);
    return 0;
}

1 1 2 5 14 42 132 429 1430
1
1 1 2 5 14

#include <stdio.h>
 
int main(void) {
    long binom[8][8] = {{0}};
    for (int n = 0; n < 8; n++) {
        binom[n][0] = 1;
        for (int k = 1; k <= n; k++) binom[n][k] = binom[n - 1][k - 1] + (k <= n - 1 ? binom[n - 1][k] : 0);
    }
    long l[7] = {1};
    for (int n = 1; n <= 5; n++) {
        long s = 0;
        for (int k = 0; k < n; k++) s += binom[n - 1][k] * l[k] * l[n - 1 - k];
        l[n] = n * s;
    }
    long c[6] = {1}, fact = 1;
    for (int n = 1; n <= 5; n++) {
        c[n] = 0;
        for (int i = 0; i < n; i++) c[n] += c[i] * c[n - 1 - i];
    }
    int ok = 1;
    for (int n = 1; n <= 5; n++) {
        fact *= n;
        ok = ok && l[n] == fact * c[n];
    }
    printf("%ld %ld %ld %ld %ld\n%d\n", l[1], l[2], l[3], l[4], l[5], ok);
    return 0;
}

1 4 30 336 5040
1

#include <stdio.h>
 
int main(void) {
    long c[6] = {1};
    for (int n = 1; n <= 5; n++) {
        c[n] = 0;
        for (int i = 0; i < n; i++) c[n] += c[i] * c[n - 1 - i];
    }
    long total = 0;
    for (int k = 1; k <= 5; k++) {
        long w = c[k - 1] * c[5 - k];
        total += w;
        printf("%ld ", w);
    }
    printf("%ld\n", total);
    return 0;
}

14 5 4 5 14 42

#include <stdio.h>
 
static int n, p[8];
 
static int count(int used, int k) {
    if (k == n) return 1;
    int t = 0;
    for (int v = 1; v <= n; v++) {
        if (used & (1 << v)) continue;
        if (k > 0 && p[(k - 1) / 2] < v) continue;
        p[k] = v;
        t += count(used | (1 << v), k + 1);
    }
    return t;
}
 
int main(void) {
    for (n = 3; n <= 7; n++) printf("%d ", count(0, 0));
    printf("\n");
    return 0;
}

2 3 8 20 80

#include <stdio.h>
 
static long a[8][9];
 
int main(void) {
    for (int h = 0; h <= 8; h++) a[0][h] = 1;
    for (int n = 1; n <= 7; n++)
        for (int h = 1; h <= 8; h++)
            for (int i = 0; i < n; i++) a[n][h] += a[i][h - 1] * a[n - 1 - i][h - 1];
    for (int h = 3; h <= 5; h++) printf("%ld ", a[5][h] - a[5][h - 1]);
    printf("\n");
    for (int h = 3; h <= 7; h++) printf("%ld ", a[7][h] - a[7][h - 1]);
    printf("\n");
    return 0;
}

6 20 16
1 68 152 144 64

Cheat box

Traps and GATE patterns

Connections

Counting trees uses the same sum-of-products idea as recurrence relations. The connection to stack-sortable permutations is on the stack and construction pages, and the order counts are used for the binary search tree and the binary heap. The basic facts that this page builds on are on the trees page.

PYQs

The height of a binary tree is the number of edges
in the longest path from the root to a leaf in the tree.
The maximum possible height of a full binary tree
with 23 nodes is
. (answer in integer)

Let T be a full binary tree with 8 leaves. (A full
binary tree has every level full.) Suppose two
leaves a and b of T are chosen uniformly and
independently at random. The expected value of the
distance between a and b in T (i.e., the number of
edges in the unique path between a and b) is
(rounded off to 2 decimal places)

Let T be a binary search tree with 15 nodes. The
minimum and maximum possible heights of T are:
Note: The height of a tree with a single node is 0.

A binary tree T has 20 leaves. The number of nodes
in T having two children is
.

The number of ways in which the numbers 1, 2, 3, 4,
5, 6, 7 can be inserted in an empty binary search tree,
such  that  the  resulting  tree  has  height  6,  is

DATA STRUCTURE

Note: The height of a tree with a single node is 0.
[This question was originally a Fill-in-the-Blanks
question]

Consider a binary tree T that has 200 leaf nodes.
Then, the number of nodes in T that have exactly two
children are

The height of a tree is the length of the longest root-
to-leaf path in it. The maximum and minimum
number of nodes in a binary tree of height 5 are

The height of a binary tree is the maximum
number of edges in any root to leaf path. The
maximum number of nodes in a binary tree of
height h is:

The maximum number of binary trees that can be
formed with three unlabeled nodes is:

A complete n-ary tree is a tree in which each node
has n children or no children. Let I be the number
of internal nodes and L be the number of leaves in
a complete n-ary tree. If L = 41, and I = 10, what
is the value of n?

How many distinct binary search trees can be
created out of 4 distinct keys?

In a complete k-ary tree, every internal node has
exactly k children. The number of leaves in such a
tree with n internal nodes is:

Self-check

Revision card

References