95. Unique Binary Search Trees II

Description

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

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: 3

Output:

[

[1, null, 3, 2],

[3, 2, null, 1],

[3, 1, null, null, 2],

[2, 1, 3],

[1, null, 2, null, 3]

]

Explanation:

The above output corresponds to the 5 unique BST's shown below:

Solutions

TreeNode

// Definition for a binary tree node.
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;
    }
}

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public List<TreeNode> generateTrees(int n) {
        if(n < 1) {
            return Collections.EMPTY_LIST;
        }
        List<TreeNode>[][] dp = new ArrayList[n+1][n+1];
        return generateTrees(1, n, dp);
    }
    
    private List<TreeNode> generateTrees(int start, 
                                         int end, 
                                         List<TreeNode>[][] dp) {
        List<TreeNode> allTrees = new ArrayList<TreeNode>();
        if(start > end) {
            allTrees.add(null);
            return allTrees;
        }
        
        if(dp[start][end] != null) return dp[start][end];
        
        for(int i = start; i <= end; i++) {
            // all possible left subtrees if i is choosen to be a root
            List<TreeNode> leftTrees = generateTrees(start, i-1, dp);
            
            // all possible right subtrees if i is choosen to be a root
            List<TreeNode> rightTrees = generateTrees(i+1, end, dp);
            
            // connect left and right trees to the root i
            for(TreeNode leftTree: leftTrees) {
                for(TreeNode rightTree: rightTrees) {
                    TreeNode currentTree = new TreeNode(i);
                    currentTree.left = leftTree;
                    currentTree.right = rightTree;
                    allTrees.add(currentTree);
                }
            }
        }
        
        dp[start][end] = allTrees;
        
        return allTrees;
    }
}

Follow up