Categories: Combinatory

Number of Binary trees possible with n nodes

What is the no. of distinct binary trees possible with n labeled nodes?

Solution

$ \frac{(2n)!} { (n+1)!}$

(Proof to be Added)

What is the no. of distinct binary trees possible with n unlabeled nodes? (No. of structurally different binary trees possible with n nodes)

Solution

If the nodes are similar (unlabeled), then the no. of distinct binary trees will be the above value divided by the no. of distinct permutations possible for a binary tree structure, which will be $n!$ for a tree with $n$ nodes.

$ \frac{(2n)!} { (n+1)! n!}$

=$\frac{2nCn}{n+1}$

(This is the $n^{th}$ Catalan number)

What is the no. of distinct binary search trees possible with n nodes?

Solution

Counting the no. of distinct binary search trees possible for n nodes, is similar to counting the no. of distinct binary trees possible for n nodes assuming nodes are unlabeled. Hence, this value will also be

=$\frac{2nCn}{n+1}$

($n^{th}$ Catalan number)

Alternatively, for each valid binary search tree, we can get $n!$ binary trees by permuting the vertices, of which only 1 permutation is a$BST$. Hence, the total no. of binary search trees possible with $n$ nodes will be

$\frac{\text{No. of distinct binary trees with $n$ distinct nodes}} {n!}$

= $ \frac{(2n)!} { (n+1)! n!}$

=$\frac{2nCn}{n+1}$

($n^{th}$ Catalan number)

(We can also use the fact that for a given tree structure, there can be only 1 $BST$. Hence, no. of different $BST$s with n nodes will be equal to the no. of different binary tree structures possible for n nodes)

arjun

View Comments

Leave a Comment
Share
Published by
arjun
Tags: binary treecombinatoryno. of nodes
8 years ago

Recent Posts

GATE CSE 2022 Admissions, Results and Placement Responses

This page shows all details regarding GATE CSE 2022 Admissions including results, admission offers and…

2 years ago

GATE CSE 2021 Admission Responses

Source Add your Response Rank Predictor for GATE CSE 2021 Result Responses: GATE CSE 2021…

3 years ago

GATE CSE Books – More Options

Best Books for GATE CSE with Relevant Chapters to Read  Heads Up! These GATE CSE…

3 years ago

ISI PCB Previous Year Papers with Solution

Indian Statistical Institute(ISI) offers M Tech in Computer Science with the Admission Test Codes MMA/PCA…

3 years ago

ISI JRF Previous Year Papers with Solution

Indian Statistical Institute(ISI) offers Junior Research Fellowships (JRF) in Computer Science, Statistics, Mathematics, Quantitative Economics,…

3 years ago

ISI DCG Previous Year Papers with Solution

 Indian Statistical Institute(ISI) conduct the admission test for Postgraduate Diploma in Computer Applications(PGDCA) with the…

3 years ago

How to use GO?

Categories

Recent Posts

GATE Overflow

Meta

  • GATE Overflow
  • Aptitude Overflow
Answered: ACE TOC Test

B,c are eliminated as they can't generate empty string A can't generate only 1 So D is answer [...]

Answered: PhD Admissions Written Test (Basic)

In mathematics such pairs $(A[i], i)$ are known as fixed points. All this problem asks is that given a non-strict monotone sequence find all its fixed points. The fastest algorithm would be Binary Search with a sanity check to remove collisons with duplicate elements for if the returning value in the search is same as the returnee (i.e, the base case would need a check), still a O(1) check.So assuming the array is already available, the time complexity would be $O(\text{log} \;n)$ [...]

Answered: GATE DS&AI 2024 | Question: 35

Bubble sort needs 3. Insertion sort wastes 1 to assume first element as sorted. Selection sort does it in 2 with first pass swap [4, 1] and second pass swap [3, 2]. So B.   [...]

Answered: GATE CSE 2022 | Question: 38

Ans : B,C,D are false L1 is classic example of not CFL . But Compliment of {WW} is CFL . L2 is DCFL as for every b we will pop a and will do nothing on c . L3 is DCFL as for every c we will pop b do nothing on a. CFL/DCFL  is not closed under Intersection .   [...]

Answered: GATE Electrical 2023 | GA Question: 9

Although with cyclicity this would be easy. Here is an alternative using binomial theorem only: $3^{999} \equiv 3 (10 - 1)^{499} \equiv 3 (10 - 1) \equiv - 3 \equiv 7 \text{ mod } 10$ and $7^{1000} \equiv (10 -3)^{1000} \equiv (-1)^{1000} (3)^{1000} \equiv (10 - 1)^{500} \equiv 1 \text { mod 10}$ Now $(3^{999} \times 7^{1000}) \text { mod }  10 \equiv \left[(3^{999} \text{ mod } 10) \times (7^{1000} \text{ mod } 10)\right] \text { mod 10 } \equiv 7 \text { mod } 10 \equiv 7.$ [...]

Answered: B tree dbms

In the first level = 19 index In the second level = (20) * 19 = 380 In the third level = (20*20) * 19 = 7600 Total = 7999 I have seen this question many times seems like the options are wrong all other answers were also giving the same result. [...]

Answered: CAT 2015 | Question: 31

c [...]

Answered: CAT 2023 Set-3 | Quantitative Aptitude | Question: 2

B [...]

Answered: CAT 2023 Set-3 | Quantitative Aptitude | Question: 3

d [...]

Answered: CAT 2023 Set-3 | Quantitative Aptitude | Question: 5

9 [...]

Answered: CAT 2023 Set-3 | Quantitative Aptitude | Question: 1

B [...]

Answered: CAT 2020 Set-3 | Question: 52

Given information: - Dick is thrice as old as Tom. Let Tom's age be x. - Harry is twice as old as Dick. - Dick's age is 1 year less than the average age of all three. Step 1: Express Dick's age in terms of Tom's age (x). Dick's age = 3x Step 2: Express Harry's age in terms of Dick's age. Harry's age = 2 × Dick's age = 2 × 3x = 6x Step 3: Set up an equation for Dick's age being 1 year less than the average age of all three. Dick's age = (Tom's age [...]