CareerCup

Seriously I dont understand why people have got various answers for same problem.

Binary Tree : 2^n - n
BST : (2n)C(n)/(n+1) i.e catalan number which is same as (2n)!/( (n!)*(n+1)! )

6 binary trees, 1 binary search tree

binary tree-> (2^n)-n
BST-> (2n)C(n)/(n+1) its catalan number

binary tree-> (2^n)-n
BST-> (2n)C(n)/(n+1) its catalan number

Both will be same. In binary tree the layout matters, but the position doesn't. 1-2-3 is same as 2-1-3. In BST position matters, but the structure is constrained.

According to how I'm understanding the question, it's actually 5 distinct BSTs and 5*3! = 30 distinct binary trees. It all depends on what you count as a distinct tree though.

The reasoning is this: there are 5 ways to arrange the nodes, if you count a tree like

x
    /   \
  x     x

to be distinct from

x
  \
   x
    \
     x

(The differing view could be is that they're both a line, in which case there's only 1 way to arrange 3 nodes, as every configuration is reducible to a line for n=3. But let's not go with this interpretation of the problem.)

These 5 distinct trees can have any permutation of 1, 2, and 3 assigned to them if it's just a binary tree. If it's a binary search tree, the values of the nodes are required to be in sorted order when in-order traversal is done, which means that for each tree shape, there's only one possible configuration of the values of the nodes (the i-th node in the in-order traversal must have the value i).

Therefore, I take the answer to be 5 for BSTs and 5*3! =30 for arbitrary binary trees.