The Gateway to Computer Science Excellence

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?**

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

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

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

Without labels it is just a binary tree..

52,345 questions

60,503 answers

201,884 comments

95,331 users