The number of possible ordered trees with three nodes A,B,C is?
How to solve it
since it is about all possibilities having all three nodes there are 12 such ordered tree 6 are binary and 6 are skewed trees
(2ncn/(n+1)) * n! n =no of nodes so substitute n=3 answer is 30 .But there is no option 30
This is simple. At 1st split the problem into two parts - A) Tree with 3 nodes i.e root node has two children & B) Tree with 2 nodes i.e root has one child. Now consider case 'A'. Here look root node is fixed and remaining two child nodes are able to interchange their positions. As example Let A is root node and B,C are child nodes. Now B can be left child & C can be right child. Alternatively B can be right and C can be left. So they can interchange their positions in 2! ways. Similarly If we consider B as root then we get another 2! and in case of C as root got another 2!. So from case 'A' we got total 2!+2!+2! = 6 number of distinct ordered trees. Now lets go to case 'B'. Here it's all about root and exactly one child i.e just 2 nodes. So here the node combinations are A-B,B-C,C-A & like the case 'A' for A-B we got 2!, for B-C: 2! & for C-A: 2!. So in case 'B' also total 2!+2!+2! = 6 number of distinct ordered trees. Now we have come to the final part. If you look carefully, then you find that case 'A' & 'B' are non-overlapping cases as we consider distinct suit of conditions for each case respectively. So now simply add the results we got from case 'A' & 'B' i.e 6+6 = 12. Therefore, we can conclude now by our final result as 12. :) :)
HOW TO SOLVE IT
- [A] X
- [B] null
- [C] s
- [D] none of these
- [A] Optimal binary search tree construction can be performed efficiently using dynamic programming.
- [B] Breath first search cannot be used to find converted components of a graph.
- [C] Given the prefix and post fix walks over a binary tree.The binary tree cannot be uniquely constructe
- [D] Depth first search can be used to find connected components of a graph.
- [A] mn
- [B] max(m,n)
- [C] min(m,n)
- [D] m+n-1
- [A] 2 deletions and 3 additions
- [B] 3 additions and 2 deletions
- [C] 3 deletions and 3 additions
- [D] 3 deletions and 4 additions