0

What is the number of different binary trees and Binary search trees that can be formed from n nodes? Pls Note : 1) I am asking for Binary trees and not full Binary trees (in which case the answer is Catalan(n))? 2) In case of BST's again pls include all the cases (including linear chains)

I think (expect) that Ans1 = Ans 2 * factorial (n), as each structure would only entail a single arrangement of keys as per BST ordering

Guy Coder
  • 24,501
  • 8
  • 71
  • 136
Parikshit Khanna
  • 39
  • Could you please provide some examples of what this function should do? Something like `f(1) = x because ..., f(2) = y because ..., f(3) = z because ...` – michaelsnowden Oct 20 '15 at 17:27
  • Possible duplicate of [With ' N ' no of nodes, how many different Binary and Binary Search Trees possible?](http://stackoverflow.com/questions/3042412/with-n-no-of-nodes-how-many-different-binary-and-binary-search-trees-possib) – michaelsnowden Oct 20 '15 at 17:28
  • @michaelsnowden : The question might be the same, but I am afraid the answers are given for FULL Binary trees – Parikshit Khanna Oct 20 '15 at 17:52
  • f(1) = 1 f(2) = 2 f(3) = 3 (right chain,left chain and the full binary tree). The only restriction I am looking for is that any node can't have a right child unless there is a left child – Parikshit Khanna Oct 20 '15 at 17:54

0 Answers0