729 views
0 votes
0 votes

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?

1 Answer

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

edited by

Related questions

4 votes
4 votes
1 answer
2
2 votes
2 votes
3 answers
4
learncp asked Jan 26, 2016
746 views
Insert the given values in the order in initially empty $\text{AVL}$ tree.$\text{34,21,10,27,24,43,15,6}$What is the value at the root of the tree$?$