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