Redirected
18,945 views
7 votes
7 votes

The number of possible ordered trees with 3 nodes A, B, C is:

(a) 16       (b) 12            (c) 6           (d) 10
 
what is ordered tree alignment?

4 Answers

4 votes
4 votes
possible ordered tree are 30(which all will be binary) as there will be 5 possible structure and each such structure can be filled in 3!=6 ways
3 votes
3 votes
A tree where the children of each node have a designated order (not necessarily based on their value) and can be referred to specifically.

The tree may be of depth 1 or 2. If depth is 2, we have 6 possibilities( 3! ). If the depth is 1, the root maybe one of the three nodes and for each root, 2 trees are possible.

Therefore, 6(depth = 1) + 6(depth = 2)  = 12.
3 votes
3 votes

I read all the answers and none projects the crux the of the problem. 

Only number of ordered trees has been asked and no where is it mentioned whether it's binary or ternary etc.

The formula n!*(2nCn)/(n+1) is for number of ordered binary trees. According to this the no. of trees should be 5 and ordering each tree

gives us 5*3!=30 trees. as shown below:-

BUT that's not the question !!! 

The only trees possible are trees with height 1 and trees with height 2. 

 THEREFORE THE ANSWER IS 12 TREES.

0 votes
0 votes
b)12

The tree maybe of depth 2 or 1. If depth is 2, we have 6 possible trees. This is because one of the 3 nodes A, B, C may be the root and the next level may be one of the remaining 2 nodes. If the depth is 1, the root maybe one of the 3 nodes A, B, C. Corresponding to a root, say A, 2 trees are possible as this.

                                        A                 and                  A

                              B                  C                      C                B

This gives us 6 more possibilities.

Total = $12$

Related questions

0 votes
0 votes
0 answers
1
Shivangi Parashar 2 asked Aug 28, 2018
473 views
0 votes
0 votes
0 answers
2
ankitgupta.1729 asked Apr 11, 2018
1,414 views
How many total Homeomorphically Irreducible Trees are possible with 'n' nodes ?
1 votes
1 votes
1 answer
3
Himani Srivastava asked Oct 16, 2015
7,846 views
amount of time it would take to send 500 packets using 6-packet size window and without sliding window will be, when the time to send in one direction is 5 ms31000, 50004...
0 votes
0 votes
1 answer
4
Chaitanya Kale asked Aug 31, 2022
415 views
In GATE if questions just mention a tree then should we assume it to be a directed or undirected tree?Also, if we are having an undirected tree then does the child node c...