Number of Binary Trees for given Preorder Sequence length
Count the number of Binary Tree possible for a given Preorder Sequence length n.
Input : n = 1 Output : 1 Input : n = 2 Output : 2 Input : n = 3 Output : 5
Background :
In Preorder traversal, we process the root node first, then traverse the left child node and then right child node.
For example preorder traversal of below tree is 1 2 4 5 3 6 7
Finding number of trees with given Preorder:
Number of Binary Tree possible if such a traversal length (let’s say n) is given.
Let’s take an Example : Given Preorder Sequence –> 2 4 6 8 10 (length 5).

 Assume there is only 1 node (that is 2 in this case), So only 1 Binary tree is Possible
 Now, assume there are 2 nodes (namely 2 and 4), So only 2 Binary Tree are Possible:

 Now, when there are 3 nodes (namely 2, 4 and 6), So Possible Binary tree are 5
NOTE* Since we have already calculated for 1, 2 and 3 nodes. We don’t need to evaluate them again for successive nodes.

 Consider 4 nodes (that are 2, 4, 6 and 8), So Possible Binary Tree are 14.
Let’s say BT(1) denotes number of Binary tree for 1 node. (We assume BT(0)=1)
BT(4) = BT(0) * BT(3) + BT(1) * BT(2) + BT(2) * BT(1) + BT(3) * BT(0)
BT(4) = 1 * 5 + 1 * 2 + 2 * 1 + 5 * 1 = 14
 Consider 4 nodes (that are 2, 4, 6 and 8), So Possible Binary Tree are 14.
 Similarly, considering all the 5 nodes (2, 4, 6, 8 and 10). Possible number of Binary Tree are:
BT(5) = BT(0) * BT(4) + BT(1) * BT(3) + BT(2) * BT(2) + BT(3) * BT(1) + BT(4) * BT(0)
BT(5) = 1 * 14 + 1 * 5 + 2 * 2 + 5 * 1 + 14 * 1 = 42
Hence, Total binary Tree for Preorder sequence of length 5 is 42.
We use Dynamic programming to calculate the possible number of Binary Tree. We take one node at a time and calculate the possible Trees using previously calculated Trees.

// C++ Program to count possible binary trees
// using dynamic programming
#include <bits/stdc++.h>
using
namespace
std;
int
countTrees(
int
n)
{
// Array to store number of Binary tree
// for every count of nodes
int
BT[n + 1];
memset
(BT, 0,
sizeof
(BT));
BT[0] = BT[1] = 1;
// Start finding from 2 nodes, since
// already know for 1 node.
for
(
int
i = 2; i <= n; ++i)
for
(
int
j = 0; j < i; j++)
BT[i] += BT[j] * BT[i  j  1];
return
BT[n];
}
// Driver code
int
main()
{
int
n = 5;
cout <<
"Total Possible Binary Tree are : "
<< countTrees(n) << endl;
return
0;
}
Output:
Total Possible Binary Tree are : 42
Alternative :
This can also be done using Catalan number Cn = (2n)!/(n+1)!*n!
For n = 0, 1, 2, 3, … values of Catalan numbers are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …. So are numbers of Binary Search Trees.
Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growthoriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at
http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide