algoadvance

Leetcode 95. Unique Binary Search Trees II

Problem Statement

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 to n.

Clarifying Questions

Before proceeding, let’s clarify a few points to ensure we understand the problem requirements:

  1. Input Constraints: What is the maximum value for n?
    • This typically helps in understanding if the solution needs to be highly optimized.
  2. Output Format: How should the trees be represented in the output? Are they represented as TreeNode objects or some other structure?
    • Usually, problems like these expect a list of TreeNode objects, but it’s always good to confirm.

Let’s assume:

TreeNode Class Definition (In case needed)

Let’s assume the definition of TreeNode is as below (commonly used in LeetCode problems):

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

Strategy

  1. Recursion: We’ll use recursion to solve this problem. The idea is to consider each number from 1 to n as the root and recursively generate all possible left and right subtrees.

  2. Divide and Conquer: When a number i is chosen as the root, the numbers from 1 to i-1 form the left subtree, and the numbers from i+1 to n form the right subtree. We’ll recursively generate all unique subtrees for each possible root.

  3. Merging Trees: For each possible left subtree and each possible right subtree, we create a new tree with the current number as the root.

  4. Base Case: If start > end, return a list containing null (indicating no subtree).

Code

Here’s how to implement this in Java:

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

public class Solution {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public List<TreeNode> generateTrees(int n) {
        if (n == 0) return new ArrayList<>();
        return generateTrees(1, n);
    }
    
    private List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> allTrees = new ArrayList<>();
        if (start > end) {
            allTrees.add(null);
            return allTrees;
        }
        
        for (int i = start; i <= end; i++) {
            List<TreeNode> leftTrees = generateTrees(start, i - 1);
            List<TreeNode> rightTrees = generateTrees(i + 1, end);
            
            for (TreeNode left : leftTrees) {
                for (TreeNode right : rightTrees) {
                    TreeNode currentTree = new TreeNode(i);
                    currentTree.left = left;
                    currentTree.right = right;
                    allTrees.add(currentTree);
                }
            }
        }
        
        return allTrees;
    }
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        List<TreeNode> result = solution.generateTrees(3);
        // Add code to print the result if needed
    }
}

Time Complexity

This problem has a catalan number growth rate because it involves generating all possible BSTs:

So, the time complexity for generating all unique BSTs is (O(C_n)), which is the nth Catalan number.

Conclusion

The solution utilizes recursive tree generation with divide and conquer methodology to generate all unique BSTs for a given number n. The resulting trees are returned as a list of TreeNode objects.

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