Number of distinct binary trees

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

Edit Distance

Problem description:

Given two strings A and B, find the minimum number of operations needed to transform A into B, there are only three valid operations:

-Replace a character
-Delete a character
-Insert a character

Examples:

A = “hello”
B = “hola”
result = 3, the operations were:
1.- replace ‘e’ with ‘o’   -> “hollo”
2.- replace ‘l’ with ‘a’   -> “holao”
3.- remove ‘o’             -> “hola”

Solution:

So for this problem we have two strings A and B, let’s work with the following example:

A = "abc"
     i
B = "cba"
     j

Remember that we want to transform A into B, any operation has to be done over A.

We are gonna use indexes i and j to loop through the strings and compare them character by character so that at every step we have the following options:

First index i and index j are both at position 0, so we have ‘a’ and ‘c’, since they are different we have three options here:
1.- remove ‘a’ (i + 1,  j)               -> “bc”
2.- insert ‘c’ into A (i, j + 1)         -> “cabc”
3.- replace ‘a’ with ‘c’ (i + 1, j + 1) -> “cbc”

Why don’t we just try them all?

int minDistance(String word1, String word2) {
    int dp[][] = new int[word1.length() + 1][word2.length() + 1];
    for(int i = 0; i <= word1.length(); ++i)
        for(int j = 0; j <= word2.length(); ++j)
            dp[i][j] = -1;
    return getDistance(word1, word2, word1.length(), word2.length(), dp);
}
int getDistance(String word1, String word2, int i, int j, int [][]dp) {
    if(i == 0) return j;
    if(j == 0) return i;
    if(dp[i][j] >= 0) return dp[i][j];

    if(word1.charAt(i - 1) == word2.charAt(j - 1))
        return dp[i][j] = getDistance(word1, word2, i - 1, j - 1, dp);
    else
        return dp[i][j] = 1 + Math.min(getDistance(word1, word2, i - 1, j - 1, dp),
        Math.min(getDistance(word1, word2, i - 1, j, dp), getDistance(word1, word2, i, j - 1, dp)));
 }

The dp table is very important in this problem, it is used to avoid a sub task to be computed more than once, otherwise our program would run very very slow.