Question 8139 – Programming
December 8, 2023Question 16144 – Programming
December 8, 2023Question 1255 – Data-Structures
The catalan number for generating different binary trees is given by:
Correct Answer: A
Question 307 Explanation:
→ In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively-defined objects. They are named after the Belgian mathematician Eugène Charles Catalan (1814–1894).
→ Total number of possible Binary Search Trees with n different keys
BST(n)=Cn=(2n)!/(n+1)!*n!
For n = 0, 1, 2, 3, … values of Catalan numbers are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ….
So are numbers of Binary Search Trees.
→ Total number of possible Binary Trees with n different keys BT(n)=BST(n)*n!
→ Total number of possible Binary Search Trees with n different keys
BST(n)=Cn=(2n)!/(n+1)!*n!
For n = 0, 1, 2, 3, … values of Catalan numbers are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ….
So are numbers of Binary Search Trees.
→ Total number of possible Binary Trees with n different keys BT(n)=BST(n)*n!
!2n / (!n*!(n+1))
C(n,2n) (n+1)
!n*C(2n,n) (n+1)
C(2n,n)/ !n
Subscribe
Login
0 Comments