[LeetCode] Unique Binary Search Trees II

Problem: Given an integer n, return all the structurally unique BST's (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.

Example:

Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

Input: n = 1
Output: [[1]]

Constraints:

• 1 <= n <= 8

Approach: The intuition is to take each number i from 1...n as root and then because we need to create BST, we know that left subtree will have numbers 1...i - 1 and right subtrees will have i + 1...n. With this intuition, here is our algorithm:

• DEFINE generate_tree (start, end)
• result = new list()
• IF start > end
• RETURN new List {null}
• FOR i = 1 TO n
• leftTrees = generate_tree (start, i - 1) // recursively make all left subtrees
• rightTrees = generate_tree (i + 1, end) // recursively make all right subtrees
• FOR j = 0 TO leftTrees.Length
• FOR k = 0 TO rightTrees.Length
• Node node = new Node(i)
• node.left =  leftTrees[j]
• node.right = rightTrees[k]
• result.Add(node)
• return result

Implementation in C#:

    public IList<TreeNode> GenerateTrees(int n) 

    {

        if (n <= 0)

        {

            return new List<TreeNode>();

        }

        return this.GenerateTrees(1, n);

    }

    

    private List<TreeNode> GenerateTrees(int start, int end)

    {

        List<TreeNode> result = new List<TreeNode>();

        if (start > end)

        {

            result.Add(null);

            return result;

        }

        for (int i = start; i <= end; ++i)

        {

            List<TreeNode> leftTrees = this.GenerateTrees(start, i - 1);

            List<TreeNode> rightTrees = this.GenerateTrees(i + 1, end);

            

            for (int j = 0; j < leftTrees.Count; ++j)

            {

                for (int k = 0; k < rightTrees.Count; ++k)

                {

                    TreeNode node = new TreeNode(i);

                    node.left =  leftTrees[j];

                    node.right = rightTrees[k];

                    result.Add(node);

                }

            }

        }     

        return result;

    }

Complexity: O(number of BSTs) = O(nth Catalan number) = O((2n)!/((n+1)!*n!))