The Gateway to Computer Science Excellence
0 votes
135 views

1. How many Binary trees can be made with:

(a) 3 unlabelled nodes?

(b) 3 labelled nodes?

2. How many Binary Search trees can be made with:

(a) 3 unlabelled nodes?

(b) 3 labelled nodes?

3. How many AVL trees can be made with:

(a) 3 unlabelled nodes?

(b) 3 labelled nodes?

Can these be generalised for 'n' nodes?

in DS by Boss (15.1k points) | 135 views

1 Answer

+3 votes

How many Binary trees can be made with :-

1) Un- labeled :- There is a formula called CATALAN NUMBER = $\frac{\binom{2n}{n}}{n+1}$

        Called them as patterns

2) labeled :- for each pattern above, there are n! trees ===> total = $\frac{\binom{2n}{n}}{n+1} * n! $


How many Binary Search trees can be made with :-

1) Un- labeled :- There is a formula called CATALOG NUMBER = $\frac{\binom{2n}{n}}{n+1}$

        Called them as patterns

2) labeled :- for each pattern above, there only 1 way to labeled the nodes of the tree ===> total = $\frac{\binom{2n}{n}}{n+1} $


How many AVL trees can be made with :-

1) with 3 un-labeled nodes:- only one way ( i don't know general formula for un-labeled )
 

2) labeled :- for each pattern above, there only 1 way to labeled the nodes of the tree ===> total = No.of trees with un-labeled.

by Veteran (64k points)
edited by
+2
Minor correction -- the number you are referring to you is called the Catalan number.
0
How can a binary search tree be unlabelled?

We can form a Bst only when it is labelled with values.

Without labels it is just a binary tree..
0

@Human

yes,you are absolutely right.... without labeling you can't decide it is Binary tree or Binary search tree

But why i wrote unlabeled trees is " First we have to take a pattern and Fix it, then it lead to unique BST"

For simple calculation purpose only, i used it

0
Ok brother.

Related questions

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
50,666 questions
56,170 answers
193,841 comments
94,047 users