algoadvance

Leetcode 95. Unique Binary Search Trees II

Problem Statement

The task is to generate all unique binary search trees (BSTs) that store values 1 to n.

Clarifying Questions

Before diving into the solution, we should clarify a few things:

  1. Are we guaranteed the input n is always a positive integer?
  2. Is there an upper limit on the value of n?
  3. Should the BSTs be returned in any specific order? (usually not necessary to ask, but good to double-check)
  4. What should be the structure of the output?

For this problem, let’s assume:

  1. Yes, n is always a positive integer.
  2. The value of n is reasonably small, typically up to about 9 or 10 for practical purposes.
  3. No specific order is required for the output of BSTs.
  4. The function should return a list/vector of pointers to the root nodes of the generated BSTs.

Strategy

To solve this problem, we need to generate all possible BST structures where the nodes store values from 1 to n. The key insight is to use a recursive approach where:

We will create a helper function that constructs the trees for a given range [start, end].

Code

#include <vector>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if (n == 0) return {};
        return generateTreesInRange(1, n);
    }
    
private:
    vector<TreeNode*> generateTreesInRange(int start, int end) {
        if (start > end) {
            return {nullptr};
        }
        
        vector<TreeNode*> allTrees;
        
        for (int i = start; i <= end; ++i) {
            // Generate all left and right subtrees
            vector<TreeNode*> leftTrees = generateTreesInRange(start, i - 1);
            vector<TreeNode*> rightTrees = generateTreesInRange(i + 1, end);
            
            // Combine them with the current node `i` as the root
            for (TreeNode* left : leftTrees) {
                for (TreeNode* right : rightTrees) {
                    TreeNode* currentTree = new TreeNode(i);
                    currentTree->left = left;
                    currentTree->right = right;
                    allTrees.push_back(currentTree);
                }
            }
        }
        
        return allTrees;
    }
};

Time Complexity

The time complexity is somewhat intricate to analyze due to the recursive nature of the problem. However, for a given n, the number of unique BSTs corresponds to the n-th Catalan number, which grows exponentially. Therefore, the time complexity is approximately (O(4^n / n^{3/2})). The space complexity is also dominated by the recursion stack and the storage of the trees, which is also exponential in the worst case.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI