Given n nodes. Find the number of different structural
binary trees that can be formed using the nodes.
Answers were Sorted based on User's Feedback
Answer / hitesh viradiya
m = 1 2 3 4 5 6 7 8
n=1 1
2 1 1
3 2 2 1
4 5 5 3 1
5 14 14 9 4 1
6 42 42 28 14 5 1
7 132 132 90 48 20 6 1
8 429 429 297 165 75 27 7 1
(2n)!/[(n+1)!n!]
Is This Answer Correct ? | 135 Yes | 16 No |
Answer / kathir
There are 2 pointers available for each node.
So we can have 2*n pointers totally.
Total no. of edges = n-1
So, Null pointers = n+1.
We need to choose (n-1) pointers from 2n pointers.
So the combination results in (2n)C(n-1).
We can have n distinct roots possible.
So, answer will be (2n) C (n-1) / n.
which leads to,
{2n C n}/{n+1}. ( Unlabelled )
Labelled Structured tree will be,
{2n C n}/{n+1} * {n!}
Is This Answer Correct ? | 30 Yes | 6 No |
No. of labeled binary tree :
n^(n-2)
No. unlabeled binary tree :
(2n)!/[(n+1)!.n!] (this is known as catlon number)
Is This Answer Correct ? | 25 Yes | 12 No |
Answer / atul barve
No. of labeled binary tree :
{(2n)!/[(n+1)!.n!]}*n!
No. unlabeled binary tree :
(2n)!/[(n+1)!.n!] (this is known as catlon number)
Is This Answer Correct ? | 19 Yes | 11 No |
Answer / fawad ghafoor
The number of different trees with 8 nodes is 248
2^n - n
Is This Answer Correct ? | 5 Yes | 0 No |
Answer / ajeet
int countTrees(int num)
{
if(num<=1)
return 1;
else
{
int root,left,right,sum=0;
for(root=1;root<=num;root++)
{
left=countTrees(root-1);
right=countTrees(num-root);
sum+=left*right;
}
return sum;
}
}
Is This Answer Correct ? | 5 Yes | 1 No |
Answer / sayandip ghosh
The max number of binary trees that can be formed from n
nodes is given by the Catlan Number C(n).
C(n) = (2n)! / (n+1)!*n! for n>=0.
int findNoTree(int low ,int high)
{
int sum=0;
if(low<=high)
{
for(int k=low;k<=high;k++)
{
if(k==low)
sum+=findNoTree(low+1,high);
else
{
if(k==high)
sum+=findNoTree(low,high-1);
else
sum=sum+findNoTree(low,k-1)*findNoTree(k+1,high);
}
}
return sum;
}
return 1;
}
Is This Answer Correct ? | 2 Yes | 1 No |
union u { union u { int i; int j; }a[10]; int b[10]; }u; main() { printf("\n%d", sizeof(u)); printf(" %d", sizeof(u.a)); // printf("%d", sizeof(u.a[4].i)); } a. 4, 4, 4 b. 40, 4, 4 c. 1, 100, 1 d. 40 400 4
struct aaa{ struct aaa *prev; int i; struct aaa *next; }; main() { struct aaa abc,def,ghi,jkl; int x=100; abc.i=0;abc.prev=&jkl; abc.next=&def; def.i=1;def.prev=&abc;def.next=&ghi; ghi.i=2;ghi.prev=&def; ghi.next=&jkl; jkl.i=3;jkl.prev=&ghi;jkl.next=&abc; x=abc.next->next->prev->next->i; printf("%d",x); }
Write a complete program that consists of a function that can receive two numbers from a user (M and N) as a parameter. Then print all the numbers between the two numbers including the number itself. If the value of M is smaller than N, print the numbers in ascending flow. If the value of M is bigger than N, print the numbers in descending flow. may i know how the coding look like?
main() { char *p = “ayqm”; char c; c = ++*p++; printf(“%c”,c); }
main() { int i = 3; for (;i++=0;) printf(“%d”,i); }
write a c program to Create employee record by taking details like name, employee id, address and phone number. While taking the phone number, take either landline or mobile number. Ensure that the phone numbers of the employee are unique. Also display all the details
#ifdef something int some=0; #endif main() { int thing = 0; printf("%d %d\n", some ,thing); }
what is the output of the below program & why ? #include<stdio.h> void main() { int a=10,b=20,c=30; printf("%d",scanf("%d%d%d",&a,&b,&c)); }
void main() { unsigned giveit=-1; int gotit; printf("%u ",++giveit); printf("%u \n",gotit=--giveit); }
main(){ char a[100]; a[0]='a';a[1]]='b';a[2]='c';a[4]='d'; abc(a); } abc(char a[]){ a++; printf("%c",*a); a++; printf("%c",*a); }
main() { char *a = "Hello "; char *b = "World"; clrscr(); printf("%s", strcat(a,b)); } a. Hello b. Hello World c. HelloWorld d. None of the above
Given a list of numbers ( fixed list) Now given any other list, how can you efficiently find out if there is any element in the second list that is an element of the first list (fixed list)
3 Answers Disney, Google, ZS Associates,