Unique Binary Search Trees

                                            
class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        dp[1] = 1;
        
        for (int i = 2; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        
        return dp[n];
    }
};

                                            
class Solution {
    public int numTrees(int n) {
        if (n <= 1) {
            return 1;
        }
        
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        
        return dp[n];
    }
}

                                            
class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [0] * (n + 1)
        dp[0] = dp[1] = 1
        
        for i in range(2, n + 1):
            for j in range(1, i + 1):
                dp[i] += dp[j - 1] * dp[i - j]
        
        return dp[n]

                                            
int numTrees(int n) {
    int dp[n + 1];
    dp[0] = 1;
    dp[1] = 1;
    
    for(int i = 2; i <= n; i++) {
        dp[i] = 0;
        for(int j = 1; j <= i; j++) {
            dp[i] += dp[j - 1] * dp[i - j];
        }
    }
    
    return dp[n];
}

                                            
public class Solution {
    public int NumTrees(int n) {
        if (n <= 1) {
            return 1;
        }
        
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        
        return dp[n];
    }
}

                                            
/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    dp[1] = 1;
    
    for (let i = 2; i <= n; i++) {
        for (let j = 1; j <= i; j++) {
            dp[i] += dp[j - 1] * dp[i - j];
        }
    }
    
    return dp[n];
};

                                            
function numTrees(n: number): number {
    const dp: number[] = new Array(n + 1).fill(0);
    dp[0] = 1;
    dp[1] = 1;

    for (let i = 2; i <= n; i++) {
        for (let j = 1; j <= i; j++) {
            dp[i] += dp[j - 1] * dp[i - j];
        }
    }

    return dp[n];
};

                                            
class Solution {
    /**
     * @param Integer $n
     * @return Integer
     */
    function numTrees($n) {
        $dp = array_fill(0, $n + 1, 0);
        $dp[0] = 1;
        $dp[1] = 1;

        for ($i = 2; $i <= $n; $i++) {
            for ($j = 1; $j <= $i; $j++) {
                $dp[$i] += $dp[$j - 1] * $dp[$i - $j];
            }
        }

        return $dp[$n];
    }
}

                                            
class Solution {
    fun numTrees(n: Int): Int {
        val dp = IntArray(n + 1)
        dp[0] = 1
        dp[1] = 1
        
        for (i in 2..n) {
            for (j in 1..i) {
                dp[i] += dp[j - 1] * dp[i - j]
            }
        }
        
        return dp[n]
    }
}

                                            
class Solution {
  int numTrees(int n) {
    List<int> dp = List.filled(n + 1, 0);
    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
      for (int j = 1; j <= i; j++) {
        dp[i] += dp[j - 1] * dp[i - j];
      }
    }

    return dp[n];
  }
}

                                            
func numTrees(n int) int {
    if n == 1 {
        return 1
    }
    
    dp := make([]int, n+1)
    dp[0], dp[1] = 1, 1
    
    for i := 2; i <= n; i++ {
        for j := 1; j <= i; j++ {
            dp[i] += dp[j-1] * dp[i-j]
        }
    }
    
    return dp[n]
}

                                            
# @param {Integer} n
# @return {Integer}
def num_trees(n)
    dp = Array.new(n+1, 0)
    dp[0] = 1
    dp[1] = 1

    (2..n).each do |i|
        (1..i).each do |j|
            dp[i] += dp[j - 1] * dp[i - j]
        end
    end

    return dp[n]
end

                                            
object Solution {
    def numTrees(n: Int): Int = {
        if (n <= 1) {
            return 1
        }
        
        val dp = new Array[Int](n + 1)
        dp(0) = 1
        dp(1) = 1
        
        for (i <- 2 to n) {
            for (j <- 0 until i) {
                dp(i) += dp(j) * dp(i - j - 1)
            }
        }
        
        dp(n)
    }
}

                                            
impl Solution {
    pub fn num_trees(n: i32) -> i32 {
        let mut dp = vec![0; n as usize + 1];
        dp[0] = 1;
        dp[1] = 1;

        for i in 2..=n as usize {
            for j in 1..=i {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }

        dp[n as usize]
    }
}

                                            
-spec num_trees(N :: integer()) -> integer().
num_trees(N) ->
    NumTrees = fun(0) -> 1;
                   (1) -> 1;
                   (N) when N > 1 ->
                       lists:sum([num_trees(I-1) * num_trees(N-I) || I <- lists:seq(1, N)])
                end,
    NumTrees(N).

To solve this coding challenge, we need to determine the number of structurally unique Binary Search Trees (BSTs) that can be formed using

n

nodes, where the nodes have unique values from 1 to

n

. The solution involves dynamic programming, which is a method for solving a complex problem by breaking it down into simpler subproblems and storing the results of these subproblems to avoid redundant calculations.

Explanation

Understanding the BST : A Binary Search Tree (BST) is a tree structure where each node has at most two children. The left child contains nodes with values less than the parent node, and the right child contains nodes with values greater than the parent node.
Unique BSTs : For each node
i

from 1 to
n

, we can consider it as the root of the tree. The number of unique BSTs with
i

as the root is the product of the number of unique BSTs possible with the left children (nodes 1 to
i-1

) and the number of unique BSTs possible with the right children (nodes
i+1

to
n

).
Dynamic Programming Approach :

We use a list
dp

where
dp[i]

represents the number of unique BSTs that can be constructed with
i

nodes.
Initialize
dp[0]

and
dp[1]

to 1 since there is exactly one BST with
0

nodes (an empty tree) and one BST with
1

node.
For
i

from 2 to
n

:

For each
j

from 1 to
i

:

Compute the number of unique BSTs for
i

nodes by considering
j

as the root.
The left subtree will have
j-1

nodes, and the right subtree will have
i-j

nodes.
Update
dp[i]

by adding the product of the number of unique BSTs for the left and right subtrees.

Result : The result
dp[n]

will give the number of unique BSTs that can be formed with
n

nodes.

Step-by-Step Explanation

Initialization:

Initialize a list
dp

of size
n+1

with all elements set to 0.
Set
dp[0]

and
dp[1]

to 1, as there is one unique BST for 0 and 1 node respectively.

DP Iteration:

Loop through
i

from 2 to
n

:

For each
i

, loop through
j

from 1 to
i

:

Calculate the number of trees with
i

nodes by considering each
j

as the root.
Use the formula
dp[i] += dp[j-1] * dp[i-j]

to accumulate the count.

Result:

Return
dp[n]

which contains the number of unique BSTs for
n

nodes.

Pseudocode:

                                            
# Initialize the dp array with zeros and length n+1
dp = [0] * (n + 1)

# The number of BSTs with 0 or 1 node is 1
dp[0] = dp[1] = 1

# Start filling the dp array for i from 2 to n
for i in range(2, n + 1):
    
    # For each number of nodes i, calculate the number of unique BSTs
    for j in range(1, i + 1):
        
        # dp[j-1] represents the number of unique BSTs with j-1 nodes (left subtree)
        # dp[i-j] represents the number of unique BSTs with i-j nodes (right subtree)
        dp[i] += dp[j - 1] * dp[i - j]

# Return the result stored in dp[n] which is the number of unique BSTs with n nodes
return dp[n]

The above pseudocode provides a method to calculate the number of unique BSTs using dynamic programming. It iterates over possible root nodes and combines the counts of unique BSTs for left and right subtrees. By storing intermediate results in the

dp

array, this method efficiently computes the desired result without redundant calculations.