How many number of different binary trees are possible for a given postorder (or preorder) traversal

Question

I came across the problem:

What is the number of binary trees with 3 nodes which when traversed in postorder give the sequence A,B,C?

Now 3 being small number I was quick to draw all possible binary trees and come at the conclusion that there can be 5 such binary trees for given postorder.

   C        C      C     C       C
  / \      /      /       \       \
 A   B    B      B         B       B
         /        \       /         \
        A          A     A           A

---

Then I tried to do the same for 4 nodes postorder traversal A,B,C,D. We will need D at the root. Then all A,B,C can be in the right subtree of left subtree. So there will be $2\times 5$ such formations. Let us denote this as follows:

$\underbrace{1}_{\text{root}}:\underbrace{3}_{\text{#nodes in left subtree}}:\underbrace{0}_{\text{#nodes in right subtree}} = \underbrace{5}_{\text{#tree arrangements}}$

$1:0:3=5$

Now there is another possibility that 2 nodes are in the left subtree and the 3rd one in the right subtree or vice versa. Then,

$1:2:1=2$

$1:1:2=2$

Total $= 14$

---

For 5 nodes postorder traversal A,B,C,D,E, I can get

$1:4:0=14$

$1:0:4=14$

$1:3:1=5$

$1:1:3=5$

$1:2:2=4$

Total $=42$

Though, I am able to figure out the number of binary trees required for these post orders, I am unable to come up with defining recurrence relation and any closed formula for number of binary trees possible for given post order traversal. Is such recurrence relation and closed formula possible?

Answer 1

Every binary tree (with the right number of nodes) has exactly one labelling that satisfies a given postorder labelling. So you need to find the number of binary trees. That is the famous Catalan number $C_n = \frac 1{n+1}{2n \choose n}$. Sequence A000108 in Sloane's OIES.

It has a nice recurrence, based on the fact that a tree with $n+1$ nodes has a root and the remaining nodes are distributed into two subtrees with $i$ and $n-i$ nodes respectively: $C_{n+1}=\sum_{i=0}^n C_i\,C_{n-i} $. Such a type of recurrence is called a convolution.

In fact, you have discovered this recurrence yourself! Here are your own numbers, in a slightly changed order:

$1:4:0=14 = 14 \cdot 1$

$1:3:1=5 = 5 \cdot 1$

$1:2:2=4 = 2 \cdot 2$

$1:1:3=5 = 1 \cdot 5$

$1:0:4=14 = 1 \cdot 14$