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

### Like this:

Like Loading...

*Related*