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

/ DSA / By
Spread the love
Close-up of HTML code highlighted in vibrant colors on a computer monitor.

Problem Statement:

Unique Binary Search Trees II: Given an integer n, return all structurally unique BST’s (binary search trees) that store values 1 through n. You need to construct all possible unique BSTs that can be formed with numbers from 1 to n using dynamic programming (DP).

Example:

  • Input: n = 3
  • Output:graphqlCopy code[ [1,null,2,null,3], [3,2,null,1,null], [2,1,3], [1,null,3,2], [2,null,1,null,3] ]

Complexity:

  • Time Complexity: O(n2)O(n^2)O(n2), where n is the number of nodes. This is because for each number i from 1 to n, we generate trees for the left and right subtrees recursively.
  • Space Complexity: O(n2)O(n^2)O(n2), due to the recursive calls and storage of intermediate results in the DP table.

Approach:

  1. Base Case: For n = 0 or n = 1, there is exactly one tree, either null (empty tree) or just one node.
  2. Recursive Case: To construct the trees for 1...n, select each i as the root. The left subtree will contain the nodes from 1 to i-1, and the right subtree will contain the nodes from i+1 to n.
  3. Use DP to store the results for subproblems (dp[i][j] holds all the BSTs for values from i to j).

Algorithm:

  1. Recursive Function: Define a function that generates all BSTs for the range i to j by iterating each node as the root and combining left and right subtrees.
  2. Dynamic Programming: Store the results for each subrange in a DP table to avoid redundant calculations.

Code Implementation:

1. C:

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* newNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

TreeNode** generateTrees(int n, int* returnSize) {
    if (n == 0) {
        *returnSize = 0;
        return NULL;
    }

    TreeNode*** dp = (TreeNode***)malloc((n+1) * sizeof(TreeNode**));
    for (int i = 0; i <= n; i++) {
        dp[i] = (TreeNode**)malloc((n+1) * sizeof(TreeNode*));
        for (int j = 0; j <= n; j++) {
            dp[i][j] = NULL;
        }
    }

    dp[0][0] = (TreeNode**)malloc(sizeof(TreeNode*));
    dp[0][0][0] = NULL;

    for (int len = 1; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = (TreeNode**)malloc(100 * sizeof(TreeNode*));  // Temporary allocation for trees
            int idx = 0;
            for (int root = i; root <= j; root++) {
                TreeNode** left = dp[i][root-1];
                TreeNode** right = dp[root+1][j];
                if (left == NULL) left = (TreeNode**)malloc(1 * sizeof(TreeNode*));
                if (right == NULL) right = (TreeNode**)malloc(1 * sizeof(TreeNode*));
                for (int l = 0; left[l] != NULL; l++) {
                    for (int r = 0; right[r] != NULL; r++) {
                        TreeNode* node = newNode(root+1);
                        node->left = left[l];
                        node->right = right[r];
                        dp[i][j][idx++] = node;
                    }
                }
            }
            dp[i][j] = realloc(dp[i][j], idx * sizeof(TreeNode*));
        }
    }

    *returnSize = 0;
    TreeNode** result = dp[0][n-1];
    free(dp);
    return result;
}

2. C++:

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

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

vector<TreeNode*> generateTrees(int n) {
    vector<vector<vector<TreeNode*>>> dp(n + 1, vector<vector<TreeNode*>>(n + 1));

    for (int len = 1; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = vector<TreeNode*>(100, nullptr);
            int idx = 0;
            for (int root = i; root <= j; root++) {
                vector<TreeNode*> left = dp[i][root - 1];
                vector<TreeNode*> right = dp[root + 1][j];
                for (auto l : left) {
                    for (auto r : right) {
                        TreeNode* node = new TreeNode(root + 1);
                        node->left = l;
                        node->right = r;
                        dp[i][j][idx++] = node;
                    }
                }
            }
        }
    }
    return dp[0][n - 1];
}

3. Java:

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int x) { val = x; }
    }

    public List<TreeNode> generateTrees(int n) {
        List<TreeNode>[][] dp = new List[n + 1][n + 1];

        for (int len = 1; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i][j] = new ArrayList<>();
                for (int root = i; root <= j; root++) {
                    List<TreeNode> left = dp[i][root - 1];
                    List<TreeNode> right = dp[root + 1][j];
                    for (TreeNode l : left) {
                        for (TreeNode r : right) {
                            TreeNode node = new TreeNode(root + 1);
                            node.left = l;
                            node.right = r;
                            dp[i][j].add(node);
                        }
                    }
                }
            }
        }
        return dp[0][n - 1];
    }
}

4. Python:

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def generateTrees(n: int):
    dp = [[[] for _ in range(n+1)] for _ in range(n+1)]
    
    for length in range(1, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            dp[i][j] = []
            for root in range(i, j+1):
                left = dp[i][root-1] if root > i else [None]
                right = dp[root+1][j] if root < j else [None]
                for l in left:
                    for r in right:
                        node = TreeNode(root+1)
                        node.left = l
                        node.right = r
                        dp[i][j].append(node)
    return dp[0][n-1]

5. C#:

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public IList<TreeNode> GenerateTrees(int n) {
        List<TreeNode>[][] dp = new List<TreeNode>[n + 1, n + 1];
        
        for (int len = 1; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i, j] = new List<TreeNode>();
                for (int root = i; root <= j; root++) {
                    var left = dp[i, root - 1];
                    var right = dp[root + 1, j];
                    foreach (var l in left) {
                        foreach (var r in right) {
                            var node = new TreeNode(root + 1);
                            node.left = l;
                            node.right = r;
                            dp[i, j].Add(node);
                        }
                    }
                }
            }
        }
        return dp[0, n - 1];
    }
}

6. JavaScript:

function TreeNode(val) {
    this.val = val;
    this.left = null;
    this.right = null;
}

var generateTrees = function(n) {
    // DP table to store results for subproblems
    let dp = Array.from({ length: n + 1 }, () => Array(n + 1).fill([]));

    // Fill DP table for lengths 1 to n
    for (let len = 1; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            let j = i + len - 1;
            dp[i][j] = [];
            // Try each value between i and j as the root
            for (let root = i; root <= j; root++) {
                let left = dp[i][root - 1] || [null];  // If there's no left subtree, use [null]
                let right = dp[root + 1][j] || [null];  // If there's no right subtree, use [null]

                // Combine left and right subtrees with the current root
                for (let l of left) {
                    for (let r of right) {
                        let node = new TreeNode(root + 1);
                        node.left = l;
                        node.right = r;
                        dp[i][j].push(node);
                    }
                }
            }
        }
    }

    // Return the result for trees with nodes from 1 to n
    return dp[0][n - 1];
};