DevExCode

LeetCode 95: Unique Binary Search Trees II Solution

Master LeetCode problem 95 (Unique Binary Search Trees II), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation

To solve this problem, we can use recursion. We start with a helper function that takes the range of values [start, end] and generates all possible unique BSTs within that range. For each value i in the range, we can construct a BST where i is the root. The left subtree will be constructed from values [start, i-1] and the right subtree from values [i+1, end].

We iterate over all possible values of i in the range and recursively generate all possible left and right subtrees. We combine these subtrees to form the final BST.

The base case for recursion is when start > end, in which case we return a list containing a single null node.

The time complexity of this approach is O(n^2) as we are iterating over all possible values of i for each node from 1 to n, and each recursion level processes a range of size n. The space complexity is also O(n^2) due to the recursive calls.

Solution Code

class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }
        return generateTrees(1, n);
    }
    
    public List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> result = new ArrayList<>();
        if (start > end) {
            result.add(null);
            return result;
        }
        
        for (int i = start; i <= end; i++) {
            List<TreeNode> leftSubtrees = generateTrees(start, i - 1);
            List<TreeNode> rightSubtrees = generateTrees(i + 1, end);
            
            for (TreeNode left : leftSubtrees) {
                for (TreeNode right : rightSubtrees) {
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    result.add(root);
                }
            }
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 95 (Unique Binary Search Trees II)?

This page provides optimized solutions for LeetCode problem 95 (Unique Binary Search Trees II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 95 (Unique Binary Search Trees II)?

The time complexity for LeetCode 95 (Unique Binary Search Trees II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 95 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 95 in Java, C++, or Python.

Back to LeetCode Solutions