Example: Num of BST given n keys

You have to find the number of possible binary trees given that you have n keys.

• n=1 => we can have only one tree
• n=2 => consider key 10, 11. You can have a tree with root 10 and right node 11 and one with root 11 and left node 10 => 2 trees
• n=3 => consider 10, 11, 12
  • If 10 is the root, we are left with the trees we can make with 2 keys
  • if 11 is the root, we have the trees with 10 as left, and the trees with 12 as right
  • if 12 is the root, we have the trees we can make with 10,11 on left

maxTrees(n)
    d[0..n]
    
    d[1] = 1
    
    for l = 3 to n
        for i = 1 to l
            d[l] += d[i-1] * d[l-i]
    return d[n]