95. Unique Binary Search Trees II

Intuition

For each value i as root in range [start, end], the left subtree uses [start, i-1] and the right uses [i+1, end]. The total tree count is the Catalan number. Generate all combinations by iterating over every possible root and recursively generating all left and right subtrees.

Algorithm

1Generate(start, end): if start > end, return [null].
2result = [].
3For root from start to end: leftTrees = Generate(start, root-1), rightTrees = Generate(root+1, end).
4For each (L, R) pair: create node(root, left=L, right=R), add to result.
5Return result.

Example Walkthrough

Input: n = 3

1.Root=1: left=[], right=Generate(2,3)=[{2,null,3},{3,2,null}]. 2 trees.
2.Root=2: left=[{1}], right=[{3}]. 1 tree.
3.Root=3: left=Generate(1,2)=[{1,null,2},{2,1,null}], right=[]. 2 trees.
4.Total 5 trees.

Output: 5 distinct BSTs

Common Pitfalls

•Returning [null] (a list with one null element) when start>end is critical - it means "one way to have an empty subtree".

95.cs

// Approach: Recursively enumerate each number as the root, combining all
// left and right subtree combinations from the remaining value ranges.
// Time: O(n·Catalan(n)) Space: O(n·Catalan(n))

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution
{
    public IList<TreeNode> GenerateTrees(int n)
    {
        if (n == 0)
            return new List<TreeNode>();
        return GenerateTrees(1, n);
    }

    private IList<TreeNode> GenerateTrees(int mn, int mx)
    {
        if (mn > mx)
            return new List<TreeNode> { null };

        IList<TreeNode> ans = new List<TreeNode>();

        for (int i = mn; i <= mx; ++i)
            foreach (TreeNode left in GenerateTrees(mn, i - 1))
                foreach (TreeNode right in GenerateTrees(i + 1, mx))
                {
                    TreeNode node = new TreeNode(i);
                    node.left = left;
                    node.right = right;
                    ans.Add(node);
                }

        return ans;
    }
}

Was this solution helpful?