Problem statement:

Given n nodes, how many binary trees can be formed?

example.

for n = 3 there are 5 different binary trees that can be formed:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Solution:

If we have n nodes 1, 2, 3, …, n we know that in some point every node is gonna be the root, and we also know that every node has two sub-trees, the left sub-tree and the right sub-tree, the key here is RECURSION, we can split this problem into different sub problems, let’s see it with an example:

for n = 1 we have ONE possible tree.
for n = 2 we have TWO possible trees:

   1         1 
    \       /  
     2     2

for n = 3 we have the following options:
A) zero nodes at the left sub-tree and two nodes at the right sub-tree
B) one node at left and one node at right
C) zero nodes at the right sub-tree and two nodes at the left sub-tree

          root                     root                      root
         /    \                  /       \                 /     \
numTrees(0)  numTrees(2)   numTrees(1) numTrees(1)  numTrees(2) numTrees(0)
    1      *     2       +      1     *    1      +     2      *    1       =   5 different trees

So it’s clear we are going to solve this problem recursively:

def numTrees(self, n):
    if n <= 1:
        return 1
    res = 0
    for i in range(n):
        res += self.numTrees(i) * self.numTrees(n - i - 1)
    return res