3
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ With first sentence, do you mean that "for given structure of binary tree (i.e. arrangement of nodes), there is only one assignment of values to those nodes, that can yield given postorder of those values"? $\endgroup$ – Maha Apr 9 '16 at 7:51
  • $\begingroup$ Exactly. The structure of the tree uniquely defines a postorder sequence of its nodes, recursively: left-subtree, right-subtree, root. There is only one way to match this sequence of nodes with your sequence of values. $\endgroup$ – Hendrik Jan Apr 9 '16 at 10:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.