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 |
#include<stdio.h> main() { struct xx { int x=3; char name[]="hello"; }; struct xx *s; printf("%d",s->x); printf("%s",s->name); }
main() { int x=5; clrscr(); for(;x==0;x--) { printf("x=%d\n”", x--); } } a. 4, 3, 2, 1, 0 b. 1, 2, 3, 4, 5 c. 0, 1, 2, 3, 4 d. none of the above
main() { int a=10,*j; void *k; j=k=&a; j++; k++; printf("\n %u %u ",j,k); }
main() { int (*functable[2])(char *format, ...) ={printf, scanf}; int i = 100; (*functable[0])("%d", i); (*functable[1])("%d", i); (*functable[1])("%d", i); (*functable[0])("%d", &i); } a. 100, Runtime error. b. 100, Random number, Random number, Random number. c. Compile error d. 100, Random number
main() { char string[]="Hello World"; display(string); } void display(char *string) { printf("%s",string); }
main() { char *str1="abcd"; char str2[]="abcd"; printf("%d %d %d",sizeof(str1),sizeof(str2),sizeof("abcd")); }
How will you print % character? a. printf(“\%”) b. printf(“\\%”) c. printf(“%%”) d. printf(“\%%”)
write a program to count the number the same (letter/character foreg: 's') in a given sentence.
main() { int i; printf("%d",scanf("%d",&i)); // value 10 is given as input here }
Write a prog to accept a given string in any order and flash error if any of the character is different. For example : If abc is the input then abc, bca, cba, cab bac are acceptable, but aac or bcd are unacceptable.
How do you verify if the two sentences/phrases input is an anagram using predefined functions in string.h and by using arrays?
main() { int i; float *pf; pf = (float *)&i; *pf = 100.00; printf("\n %d", i); } a. Runtime error. b. 100 c. Some Integer not 100 d. None of the above