Catalan Numbers (Part II)
In our previous article, we learned that Catalan numbers is a sequence of infinite numbers with its own property. We also went through some questions or examples that would use Catalan numbers to provide the answer. Just like square numbers or Fibonacci numbers, Catalan Numbers has its own sequence pattern. Once you realize the specific pattern of Catalan Numbers, you could tell if a problem would need it very quickly.
Now lets see how the a binary tree falls in to Catalan numbers. Given a number N, how many structurally unique binary search trees can we construct? Lets briefly go over the properties of a binary search tree(BST). In a BST, we alway start at the root(a parent node) with two child nodes. The left child node (and any of its childrens) has to and will always be less than the parent, and the right child node (and any of its childrens) has to and will always be greater than the parent. Now that we have that refresher, let us take the example of the number 3 as the N number of ways.
Now you must be questioning if there is a formula for Catalan Numbers. Pictured above is the actual formula. In mathematical terms the exclamation mark means factorial. For example, if given the number 3 for n, the top half would be 6! (factorial). Meaning the answer of the top would be 6*5*4*3*2*1 and resulting in 720. With the bottom half, it would be 4! * 3!. The fully written out version would be 4*3*2*1 * 3*2*1 and would result in 144. If we take a look of the Catalan numbers chart below, we can see that our answer matches the given number of 3.
