Unique Binary Search Trees II

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

Example:

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:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Analysis

https://leetcode.com/articles/unique-binary-search-trees-ii/

Similar thinking to Unique Binary Search Trees, the core of building a BST from sorted array 1, ..., n is to select a root, then build left subtrees and right subtrees recursively. The tricky part in this problem however, is to combine different subtrees and root node to unique BSTs.

Three loops

1. loop over start, ..., end and select i for the root node; (recursively) build left subtrees with left subsequence start, ..., i - 1; build right subtrees with right subsequence i + 1, ..., end

2. loop over left subtrees, with root node for left subtrees; TreeNode leftNode

3. loop over right subtrees, with root node for right subtrees; TreeNode rightNode

Note: create a new root has to be inside the 3rd loop, and then set root.left = leftNode, root.right = rightNode, and finally add to result list.

The number of possible BST is actually a Catalan number.

Time complexity: Catalan number G_n. This is done n times, that results in time complexity n*G_n

Catalan numbers grow as {4^n}/{n^{3/2} Thus, ​final time complexity O({4^n}/{n^{1/2})

Space complexity: keeps n*G_n Catalan trees, thus space complexity: O({4^n}/{n^{1/2})

Solution

class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) return new ArrayList<TreeNode>();

        return generateTrees(1, n);
    }
    private List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> trees = new ArrayList<TreeNode>();

        if (start > end) {
            trees.add(null);
            return trees;   
        }

        // select root, and generate sub trees recursively

        for (int i = start; i <= end; i++) {
            List<TreeNode> leftSubtrees = generateTrees(start, i - 1);
            List<TreeNode> rightSubtrees = generateTrees(i + 1, end);

            for (TreeNode leftTree : leftSubtrees) {

                for (TreeNode rightTree : rightSubtrees) {
                    TreeNode root = new TreeNode(i);
                    root.left = leftTree;
                    root.right = rightTree;
                    trees.add(root);
                }
            }
        }
        return trees;

    }
}

class Solution {
    public List<TreeNode> generateTrees(int n) {

        List<TreeNode> res1 = new ArrayList<TreeNode>();
        if(n <= 0)
        {
            return res1;
        }

        return genTree(1, n);
    }

    private List<TreeNode> genTree(int start, int end)
    {
        List<TreeNode> res = new ArrayList<TreeNode>();

        if(start > end)
        {
            res.add(null);
            return res;
        }

        if(start == end)
        {
            res.add(new TreeNode(start));
            return res;
        }

        List<TreeNode> left;
        List<TreeNode> right;

        for(int i = start; i <= end; i++)
        {
            left = genTree(start, i - 1);
            right = genTree(i + 1, end);

            for(TreeNode lnode : left)
            {
                for(TreeNode rnode : right)
                {
                    TreeNode root = new TreeNode(i);
                    root.left = lnode;
                    root.right = rnode;
                    res.add(root);
                }
            }
        }
        return res;
    }
}