Unique Binary Search Trees | Leetcode

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

---

Solution: When n is 0, the answer is 1 (a null tree), not 0. When n is 1, the answer is also 1. n=0 and n=1 form the base cases.

For the rest of the trees, we iterate i from 1 to n, and then for each i, we count how many unique trees we can form. The number of unique trees is the number of unique trees on the left side multiply by the number of unique trees on the right side.

The caching part is just to make the code complete faster.

We could have used an array of n elements as the cache, given that we are always going to lookup from 2 to n only, but using a hashmap is more generic and makes the code shorter and simpler to follow.

public class Solution {
    private static final Map<Integer, Integer> cache = new HashMap<>();
    
    public int numTrees(int n) {
        if (n <= 1) return 1;
        if (cache.containsKey(n)) return cache.get(n);
        int count = 0;
        for (int i = 1; i <= n; i++) {
            count += numTrees(i - 1) * numTrees(n - i);
        }
        cache.put(n, count);
        return count;
    }
}