The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+19 votes
2.9k views

The maximum number of binary trees that can be formed with three unlabeled nodes is:

  1. $1$
  2. $5$
  3. $4$
  4. $3$
asked in DS by Veteran (59.5k points)
edited by | 2.9k views
+2
For unlabelled tree
   T(n) = (2n)! / (n+1)!n!
Number of Labeled Tees = (Number of unlabeled trees) * n!
                       = [(2n)! / (n+1)!n!]  × n!

Useful read

https://www.geeksforgeeks.org/enumeration-of-binary-trees/

3 Answers

+22 votes
Best answer

Can be found with formula... $(2nCn/n+1)$... $n$ being the number of nodes. for the given question... where $n=3$... answer is $5$. Let me also specify here.. that number of Binary Search Trees with $n$ nodes is equal to number of unlabeled Binary trees.

http://gatecse.in/wiki/Number_of_Binary_trees_possible_with_n_nodes

answered by Boss (19.7k points)
edited by
0
What if it is labeled
+8
if its labeled, then since its only a binary tree and not BST, we multiply it with 3! (n! for n nodes)
+1
If it was BST then it would be still 5 even if it is labeled , is it not @ryan sequeira ?

correct me if wrong .
+4
yes, in case of BST the nodes can have only one arrangement, i.e sorted order
+7
In Unlabeled tree's only structure matters, what's value in node that does not matter.
1. o      2.    o       3.   o      4.    o   5.    o
      \               \           / \           /          /
       o               o       o   o      o          o  
      /                   \                  /              \
   o                      o              o                 o
With three unlabeled node, there are 5 trees. If they were labeled, then each strucure can be filled with 3! ways.
0
Yes it's okay to do it with formula but we can also do this by using permutation and combination and just by visualising and analysing as numbe of node is 3. it willbe 5.
0 votes
There are 5 binary trees maximum
answered by Boss (14.2k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,112 questions
45,619 answers
132,312 comments
49,297 users