data_structures.binary_tree.number_of_possible_binary_trees

Hey, we are going to find an exciting number called Catalan number which is use to find the number of possible binary search trees from tree of a given number of nodes.

We will use the formula: t(n) = SUMMATION(i = 1 to n)t(i-1)t(n-i)

Further details at Wikipedia: https://en.wikipedia.org/wiki/Catalan_number

Attributes

node_count

Functions

binary_tree_count(→ int)	Return the number of possible of binary trees.
binomial_coefficient(→ int)	Since Here we Find the Binomial Coefficient:
catalan_number(→ int)	We can find Catalan number many ways but here we use Binomial Coefficient because it
factorial(→ int)	Return the factorial of a number.

Module Contents

data_structures.binary_tree.number_of_possible_binary_trees.binary_tree_count(node_count: int) → int

Return the number of possible of binary trees. :param n: number of nodes :return: Number of possible binary trees

>>> binary_tree_count(5)
5040
>>> binary_tree_count(6)
95040

data_structures.binary_tree.number_of_possible_binary_trees.binomial_coefficient(n: int, k: int) → int

Since Here we Find the Binomial Coefficient: https://en.wikipedia.org/wiki/Binomial_coefficient C(n,k) = n! / k!(n-k)! :param n: 2 times of Number of nodes :param k: Number of nodes :return: Integer Value

>>> binomial_coefficient(4, 2)
6

data_structures.binary_tree.number_of_possible_binary_trees.catalan_number(node_count: int) → int

We can find Catalan number many ways but here we use Binomial Coefficient because it does the job in O(n)

return the Catalan number of n using 2nCn/(n+1). :param n: number of nodes :return: Catalan number of n nodes

>>> catalan_number(5)
42
>>> catalan_number(6)
132

data_structures.binary_tree.number_of_possible_binary_trees.factorial(n: int) → int

Return the factorial of a number. :param n: Number to find the Factorial of. :return: Factorial of n.

>>> import math
>>> all(factorial(i) == math.factorial(i) for i in range(10))
True
>>> factorial(-5)  
Traceback (most recent call last):
    ...
ValueError: factorial() not defined for negative values

data_structures.binary_tree.number_of_possible_binary_trees.node_count