WAP to Construct Fully Binary Tree From Given Number of Nodes. Efficiently

Given a number of nodes N of a binary tree , how many structurally different full binary trees are possible.
A binary tree is said to be full binary tree , if for every node in the tree there exists exactly zero or 2 children.

Example: When N = 5 , No. of possible trees = 2

{{{

o o
/ \ / \
o o o o
/ \ / \
o o o o

}}}


The idea behind this deduction is that successive applications of a binary operator can be represented in terms of a full binary tree.If there are n binary operators then there will be n+1 operands and total number of representations (which will be full binary trees) will be equal to Catalan number for 'n'.
e.g. if we take nodes as a,b,c and +,+. Then total number of nodes is 5 and total number of binary operator is 2 so total number of structurally different full binary trees is 2.
So if we simulate in the same way that how many structurally different full binary trees can be created for a given N (total number of nodes) we can observe that
N = n (number of operator) + (n+1) (number of operands)
so n = (N-1)/2
Now get the corresponding Catalan number for n, which is the answer to this question.

#include

int fact(unsigned int n)
{
if (n <= 1)k
return 1;
else
return n * fact(n-1);
}

int fully_bst(int n) //n= N-1/2
{

if(n==0||n==1)
return 1;
else return ((fact(2*n))/(fact(n+1)*fact(n)));
}

int main()
{

printf("%d ",fully_bst(2));

return 0;
}

Time Complexity O(n!)
Space Complexity O(1)
Run Here https://ideone.com/ICLYc