Unique Binary Search Trees In C,CPP,JAVA,PYTHON,C#,JS

Problem Statement: Unique Binary Search Trees (BSTs) using DP

Given a number n, return the total number of unique binary search trees (BSTs) that can be constructed using values 1 through n. The problem is asking for the number of structurally unique BSTs that can be built from n distinct nodes.

Example:

• Input: n = 3
• Output: 5
• Explanation: The 5 unique BSTs that can be formed are: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3

Time and Space Complexity:

• Time Complexity: O(n2)O(n^2)O(n2), where n is the number of nodes. This is because for each value of i (root node), we calculate the number of BSTs that can be formed on the left and right subtrees.
• Space Complexity: O(n)O(n)O(n) for storing the DP table.

Approach:

1. Base Case: For n = 0, there’s exactly one tree — the empty tree (1 way). For n = 1, there’s exactly one tree — a single node (1 way).
2. Recursive Case: For each possible root value i (from 1 to n):
   • The number of unique BSTs with root i is the product of the number of unique BSTs that can be formed from values less than i (left subtree) and the number of unique BSTs that can be formed from values greater than i (right subtree).
   • For each i, the left subtree can be formed from i-1 values, and the right subtree can be formed from n-i values.
   • This gives the recurrence: dp[n]=∑i=1ndp[i−1]×dp[n−i]dp[n] = \sum_{i=1}^{n} dp[i-1] \times dp[n-i]dp[n]=i=1∑n​dp[i−1]×dp[n−i]
   where dp[i] is the number of unique BSTs that can be formed using i nodes.
3. Dynamic Programming: Use a DP table to store the number of unique BSTs for each value of n from 0 to n. Start with the base cases (dp[0] = 1, dp[1] = 1) and fill the table iteratively.

Algorithm:

1. Initialize an array dp of size n+1 where dp[i] will store the number of unique BSTs that can be constructed using i nodes.
2. Set the base cases: dp[0] = 1 and dp[1] = 1.
3. For each i from 2 to n, calculate dp[i] using the recurrence relation.
4. The answer will be stored in dp[n].

---

Code Implementation in Multiple Languages:

1. C:

#include <stdio.h>

int numTrees(int n) {
    if (n == 0 || n == 1) return 1;

    int dp[n + 1];
    dp[0] = 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];
}

int main() {
    int n = 3;
    printf("Number of unique BSTs with %d nodes: %d\n", n, numTrees(n));
    return 0;
}

2. C++:

#include <iostream>
#include <vector>
using namespace std;

int numTrees(int n) {
    if (n == 0 || n == 1) return 1;

    vector<int> dp(n + 1, 0);
    dp[0] = 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];
}

int main() {
    int n = 3;
    cout << "Number of unique BSTs with " << n << " nodes: " << numTrees(n) << endl;
    return 0;
}

3. Java:

public class Solution {
    public int numTrees(int n) {
        if (n == 0 || n == 1) return 1;

        int[] dp = new int[n + 1];
        dp[0] = 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];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int n = 3;
        System.out.println("Number of unique BSTs with " + n + " nodes: " + solution.numTrees(n));
    }
}

4. Python:

def numTrees(n: int) -> int:
    if n == 0 or n == 1:
        return 1

    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]

# Example usage:
n = 3
print(f"Number of unique BSTs with {n} nodes: {numTrees(n)}")

5. C#:

using System;

public class Solution {
    public int NumTrees(int n) {
        if (n == 0 || n == 1) return 1;

        int[] dp = new int[n + 1];
        dp[0] = 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];
    }

    public static void Main(string[] args) {
        Solution solution = new Solution();
        int n = 3;
        Console.WriteLine($"Number of unique BSTs with {n} nodes: {solution.NumTrees(n)}");
    }
}

6. JavaScript:

function numTrees(n) {
    if (n === 0 || n === 1) return 1;

    const dp = Array(n + 1).fill(0);
    dp[0] = 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];
}

// Example usage:
let n = 3;
console.log(`Number of unique BSTs with ${n} nodes: ${numTrees(n)}`);

---

Explanation of the Code:

• Base Case: For n = 0 or n = 1, there’s exactly one tree — the empty tree or a single node.
• DP Table (dp[i]): This stores the number of unique BSTs that can be formed with i nodes.
• Recursive Formula: For each i, we compute dp[i] by summing over all possible values of the root (from 1 to i), calculating the left and right subtrees’ combinations. The formula used is: dp[i]=∑j=1idp[j−1]×dp[i−j]dp[i] = \sum_{j=1}^{i} dp[j-1] \times dp[i-j]dp[i]=j=1∑i​dp[j−1]×dp[i−j]
• Final Answer: The number of unique BSTs that can be formed with n nodes is stored in dp[n].

---

Example Output:

For n = 3, the output will be:

Number of unique BSTs with 3 nodes: 5

Each of the implementations will compute the same result using dynamic programming.