Question

How many different binary search trees can be constructed using six distinct keys?

Short answer

After making the calculations, the number of different binary search trees that can be constructed using six distinct keys is found to be 132.

Step-by-step solution

Understanding the basics of Binary Search Trees (BST)

A Binary Search Tree (BST) is a special form of binary tree where each node has a value, and all the nodes in the left subtree are less than the root, and all nodes in the right subtree are more than the root. When keys are distinct, the structure of the BST is influenced by the order in which the keys are inserted into the tree.

Understanding Catalan Numbers

The number of distinct Binary Search Trees can be calculated using the \(n^{th}\) Catalan number. The \(n^{th}\) Catalan number can be calculated by the formula: \[C_{n}=\frac{(2n)!}{(n+1)!n!}\]

Substitute value of n

Substitute \(n = 6\) into the Catalan number formula: \[C_{n}=\frac{(2*6)!}{(6+1)!6!}\]

Calculation

Calculate the numerator, denominator separately and then find the division.

Calculate Factorial using Stirling's approximation

Calculate Factorial using Stirling's approximation - \[n! \approx \sqrt{2\pi n} * \left(\frac{n}{e}\right)^n\]