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

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

2n   n   n 1

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

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

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

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

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

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

[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