With N no of nodes how many different Binary and Binary Search Trees possible

Question

For Binary trees  There s no need to consider tree node values  I am only interested in different tree topologies with  N  nodes   For Binary Search Tree  We have to consider tree node values

User · Answer

Eric Lippert recently had a very in-depth series of blog posts about this: "Every Binary Tree There Is" and "Every Tree There Is" (plus some more after that).

In answer to your specific question, he says:

The number of binary trees with n nodes is given by the Catalan numbers, which have many interesting properties. The nth Catalan number is determined by the formula (2n)! / (n+1)!n!, which grows exponentially.

User · Answer

Different binary trees with n nodes    1  n 1    2nCn    where C combination eg   n 6  possible binary trees  1 7   12C6  132

User · Answer

Total no of Binary Trees are      Summing over i gives the total number of binary search trees with n nodes     The base case is t 0    1 and t 1    1  i e  there is one empty BST and there is one BST with one node    So  In general you can compute total no of Binary Search Trees using above formula  I was asked a question in Google interview related on this formula  Question was how many total no of Binary Search Trees are possible with 6 vertices  So Answer is t 6    132  I think that I gave you some idea

User · Answer

2n   n   n 1

User · Answer

If given no  of Nodes are N Then     Different No  of BST Catalan N  Different No  of Structurally Different Binary trees are   Catalan N     Different No  of Binary Trees are N  Catalan N

User · Answer

I recommend this article by my colleague Nick Parlante  from back when he was still at Stanford    The count of structurally different binary trees  problem 12  has a simple recursive solution  which in closed form ends up being the Catalan formula which  codeka s answer already mentioned    I m not sure how the number of structurally different binary search trees  BSTs for short  would differ from that of  plain  binary trees -- except that  if by  consider tree node values  you mean that each node may be e g  any number compatible with the BST condition  then the number of different  but not all structurally different -  BSTs is infinite   I doubt you mean that  so  please clarify what you do mean with an example

User · Answer

binary tree    No need to consider values  we need to look at the structrue    Given by   2 power n  - n  Eg  for three nodes it is  2 power 3  -3    8-3   5 different structrues  binary search tree   We need to consider even the node values  We call it as Catalan Number   Given by   2n C n   n 1

User · Answer

The number of possible binary search tree with n nodes  elements items  is    2n C n     n 1      factorial  2n    factorial  n    factorial  2n - n        n   1     where  n  is number of nodes   elements items     Example    for  n 1 BST 1  n 2 BST 2  n 3 BST 5  n 4 BST 14 etc

User · Answer

The number of binary trees can be calculated using the catalan number   The number of binary search trees can be seen as a recursive solution  i e   Number of binary search trees    Number of Left binary search sub-trees     Number of Right binary search sub-trees     Ways to choose the root   In a BST  only the relative ordering between the elements matter  So  without any loss on generality  we can assume the distinct elements in the tree are 1  2  3  4        n  Also  let the number of BST be represented by f n  for n elements   Now we have the multiple cases for choosing the root    choose 1 as root  no element can be inserted on the left sub-tree  n-1 elements will be inserted on the right sub-tree  Choose 2 as root  1 element can be inserted on the left sub-tree  n-2 elements can be inserted on the right sub-tree  Choose 3 as root  2 element can be inserted on the left sub-tree  n-3 elements can be inserted on the right sub-tree           Similarly  for i-th element as the root  i-1 elements can be on the left and n-i on the right   These sub-trees are itself BST  thus  we can summarize the formula as   f n    f 0 f n-1    f 1 f n-2                 f n-1 f 0   Base cases  f 0    1  as there is exactly 1 way to make a BST with 0 nodes  f 1    1  as there is exactly 1 way to make a BST with 1 node

User · Answer

The correct answer should be 2nCn  n 1  for unlabelled nodes and if the nodes are labelled then  2nCn  n   n 1

[tree] With ' N ' no of nodes, how many different Binary and Binary Search Trees possible?

Examples related to tree

Examples related to binary-tree

Examples related to catalan