620 views
3 votes
3 votes
The no. of binary trees with 3 nodes which when traversed by post-order gives the sequence
A, B, C is:
(a) 3 (b) 9
(c) 7 (d) 5

2 Answers

Best answer
4 votes
4 votes
It should be 5

1 C is root b is left child of c and a is left child of b

2 C is root b is left child of c and a is right child of b

3 C is root b is right child of c and a is left child of b

4 C is root b is right child of c and a is right child of b

5 C is root a is left child of c and b is right child of c
selected by
0 votes
0 votes
Ans is (d)

No. of unlabelled BSTs with 'n' nodes= C(2n,n) / (n+1)

With n=3, we get 5 unlabelled BSTs or 5 BST structures.

Each structure has 3 nodes which can be arranged in 3! ways. Out of these 3! ways for each BST, only one order corresponds to the given post-order. Thus, each of the 5 BST structure has only one way in which the given post-order can be achieved.

Therefore, answer is 5.

Related questions

0 votes
0 votes
2 answers
2
sripo asked Dec 25, 2018
4,677 views
In a 3-array tree if internal nodes have exactly 3 children,the number of leaf nodes will be __ ?Does it vary for binary tree?What do you mean by internal nodes? Non roo...
1 votes
1 votes
0 answers
3
Rohit Gupta 8 asked Dec 25, 2017
1,109 views
If the average depth of a node in an $n$-node binary search tree is $O(\log{n})$, then the height of the tree is$O(n\log{n})$$O(n)$$O(\log{n})$$O(\sqrt(n\log{n}))$
0 votes
0 votes
2 answers
4
Aman Bisht asked Jun 12, 2017
1,100 views
The height of a binary tree having 'i' nodes at level 'i' considering root to be at level 1 is . where 'n' is the total no of nodes in the tree.A. O(logn)B. O(n)C. O(R...