[LeetCode] Unique Binary Search Trees I and II (Java)

Unique Binary Search Trees

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

For example,
Given n = 3, there are a total of 5 unique BST’s.

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

1
2
3
4
5

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

Unique Binary Search Trees II

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

For example,
Given n = 3, your program should return all 5 unique BST’s shown below.

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

1
2
3
4
5

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

Analysis

In “Unique Binary Search Trees”, we are only required to output the number of the trees. We know that all nodes in the left subtree are smaller than the root. And all nodes in the right subtree are larger than the root. For a integer n, we have n options to be the root. In these options, assuming i is the value that we choose to be the root. The value in left subtree are from 1 to i – 1, and the values in right subtree are from i + 1 to n. If 1 to i – 1 can form p different trees, and i + 1 to n can form q different trees, then we will have p * q trees when i is the root. In fact, the number of different trees depends on how many number to form the tree.

We can use an array to save the number of different trees that n integers can form. We fill the array from bottom to up, starting from 0 to n.

In “Unique Binary Search Trees II”, we need to generate all trees. The algorithm has the same idea. But we don’t just return the numbers. We return the trees that n integers can from. Then we use a nested for-loop to go through every possible combinations of left tree and right tree for a given root. We will do it recursively because it’s the same for the left tree and right tree of root.

Code

Unique Binary Search Trees

public class Solution {
    public int numTrees(int n) {
        int[] N = new int[n + 1];
        N[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                N[i] += N[j] * N[i - j - 1];
            }
        }
        return N[n];
    }
}

public class Solution {

public int numTrees(int n) {

int[] N = new int[n + 1];

N[0] = 1;

for (int i = 1; i <= n; i++) {

for (int j = 0; j < i; j++) {

N[i] += N[j] * N[i - j - 1];

}

return N[n];

}

Unique Binary Search Trees II

public class Solution {
    public List<TreeNode> generateTrees(int n) {
        return generateTrees(1, n);
    }
    
    public List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> list = new LinkedList<>();
        if (start > end) {
            list.add(null);
            return list;
        }
        for (int i = start; i <= end; i++) {
            List<TreeNode> lefts = generateTrees(start, i - 1);
            List<TreeNode> rights = generateTrees(i + 1, end);
            for (TreeNode left : lefts) {
                for (TreeNode right : rights) {
                    TreeNode node = new TreeNode(i);
                    node.left = left;
                    node.right = right;
                    list.add(node);
                }
            }
        }
        return list;
    }
}

public class Solution {

public List<TreeNode> generateTrees(int n) {

return generateTrees(1, n);

}

public List<TreeNode> generateTrees(int start, int end) {

List<TreeNode> list = new LinkedList<>();

if (start > end) {

list.add(null);

return list;

}

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

List<TreeNode> lefts = generateTrees(start, i - 1);

List<TreeNode> rights = generateTrees(i + 1, end);

for (TreeNode left : lefts) {

for (TreeNode right : rights) {

TreeNode node = new TreeNode(i);

node.left = left;

node.right = right;

list.add(node);

}

return list;

}

Complexity

The complexity of the first problem is $O(n^2)$.