Madeeasy test series

Question

The number of Binary Tree's with 4 nodes (1,2,3,4) where in every Binary Search tree '1' is leaf node are ________________.

Comments

https://gateoverflow.in/38149/labeled-binary-tree

---

in question it is Binary Search tree or Binary tree ????

Answer 1

The question is asking  The number of Binary Tree's (not binary search trees) with 4 nodes (1,2,3,4) where in every Binary Search tree '1' is leaf node.

Binary search tree is a type of binary tree.

So total no of binary tree possible with 4 different labeled nodes is (8C4 / 5) * 4!

Among those there are binary search trees. So no of binary search trees possible is  (8C4 / 5).

So no of binary trees which are not binary search trees is

(8C4 / 5) *4! - (8C4 / 5)

= (8C4 / 5) * (4! -1)

Now from diagram we can see that no of binary search trees where 1 is leaf node are 5.

So the answer should be (8C4 / 5) * (4! -1) + 5 = 327.

Answer 2

5 as C(3) catalon no arrange just 3 nodes (4,3,2) bst in 5 ways

Comments

I think answer should be 4