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

tree binary-tree catalan
siva picture siva · Jun 15, 2010 · Viewed 157.6k times · Source

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.

Answer

Black_Rider picture Black_Rider · Sep 21, 2012

  1. Total no of Binary Trees are = enter image description![enter image description here

  2. Summing over i gives the total number of binary search trees with n nodes. enter image description here

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. enter image description here

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...

Related questions

Difference between binary tree and binary search tree

Can anyone please explain the difference between binary tree and binary search tree with an example?

Read More
Difference between "Complete binary tree", "strict binary tree","full binary Tree"?

I am confused about the terminology of the below trees, I have been studying the Tree, and I am unable to distinguish between these trees: a) Complete Binary Tree b) Strict Binary Tree c) Full Binary Tree Please help me …

Read More
Reverse A Binary Tree (Left to Right)

I was looking at interview questions and I recently came upon one that asked you how to reverse a general binary tree, like flip it from right to left. So for example if we had the binary tree 6 / \ 3 4 / \ / \ 7 3 8 1 Reversing it …

Read More