6 years ago in Data Structure

# The number of possible ordered trees with three nodes A,B,C is?

[A] 16
[B] 12
[C] 6
[D] 10
Loading...

Attempted 547
Correct 95
Incorrect 152
Viewed 300

## Answers

Ag Arpit Gupta - 3 years ago

How to solve it

• Log in to add a comment
Vikas Sharma - 3 years ago

since it is about all possibilities having all three nodes there are 12 such ordered tree 6 are binary and 6 are skewed trees

• Log in to add a comment
Rupendrasingh Krishna - 4 years ago

(2ncn/(n+1)) * n! n =no of nodes so substitute n=3 answer is 30 .But there is no option 30

• Log in to add a comment
Subhajyoti Majumdar - 4 years ago

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. :) :)

• Log in to add a comment
KESHAV SAINI - 4 years ago

HOW TO SOLVE IT

• Log in to add a comment

## Related Questions

### Sparse matrices have ?

• [A] no zero
• [B] many zero
• [C] higher dimenstion
• [D] none

### Which of the following algorithm design technique is used in the quick sort algorithm?

• [A] Dynamic programming
• [B] Backtracking
• [C] Divide and conquer
• [D] Greedy method

### Which one of the following permutations can be obtained the output using stack assuming that the input is the sequence 1,2,3,4,5 in that order ?

• [A] 3,4,5,1,2
• [B] 3,4,5,2,1
• [C] 1,5,2,3,4
• [D] 5,4,3,1,2

### A vertex of degree one is called

• [A] padent
• [B] isolated vertex
• [C] null vertex
• [D] colored vertex

• [A] Stack
• [B] Set
• [C] List
• [D] Queue