search
Log In
0 votes
224 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 224 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.


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

2 votes
1 answer
1
209 views
The minimum number of vertices having degree $1$ in a tree of at least $10$ vertices is ______________. If we consider this question, then the first answer comes in our mind is $'2',$ right? But what if Tree isn't binary? if the root node has $9$ leaf nodes, so all those nodes having degree $1,$ right$?$ So the answer could be$:9$
asked Jan 18, 2017 in DS smartmeet 209 views
6 votes
2 answers
2
741 views
The number of BST's possible with $6$ nodes numbered $1$,$2$,$3$,$4$,$5$ and $6$ with exactly one leaf node are ....................... OR The number of BST's possible with $6$ nodes numbered $1$,$2$,$3$,$4$,$5$ and $6$ having a height of $5$ are .................… ( note :- height of a root is 0 )
asked Jan 6, 2017 in DS Çșȇ ʛấẗẻ 741 views
2 votes
4 answers
3
312 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$?$
asked Jan 26, 2016 in DS learncp 312 views
3 votes
0 answers
4
377 views
Consider a binary tree T that has 150 leaf nodes. Then the number of TOTAL nodes in T that have exactly two children are ______.
asked Jan 7, 2018 in DS iarnav 377 views
...