Problem Statement in English

You’re given an integer n. Return the number of structurally unique BST’s (binary search trees) which has exactly n nodes of unique values from 1 to n.

Approach

Using the approach from the previous problem 95. Unique Binary Trees II, and just returning the length of the resultant array runs into a time limit exceeded error. So, we need to do better.

In fact, since we don’t need to generate teh actual trees, we can use a mix of dynamic programming and some combinatorics to solve this efficiently.

Let’s consider the case where n is $8$. We can have various roots for the BST, and for each root, we can calculate the number of unique BSTs that can be formed with the left and right subtrees.

Therefore, the answer n = 8 depends on the sum of the number of unique BSTs for all possible roots from $1$ to $8$. When we pick a root k, the left subtree will have k - 1 nodes, and the right subtree will have n - k nodes.

The total number of unique BSTs with root k is the product of the number of unique BSTs that can be formed with the left and right subtrees.

Once we calculate the result for smaller roots (which is basically smaller ns), we can use those results to calculate the result for larger ns.

And we’re done!

Solution in Python


class Solution:
    def numTrees(self, n: int) -> int:
        # uniq_tree[i] will store the number of unique BSTs with i nodes.
        # Base cases: 
        # uniq_tree[0] = 1 (an empty tree)
        # uniq_tree[1] = 1 (a tree with 1 node)
        uniq_tree = [1] * (n + 1)
        
        # Build up the answer for every tree size from 2 up to n
        for nodes in range(2, n + 1):
            total = 0
            # Try every possible number from 1 to 'nodes' as the root
            for root in range(1, nodes + 1):
                # Left subtree has (root - 1) nodes
                left_subtrees = uniq_tree[root - 1]
                
                # Right subtree has (nodes - root) nodes
                right_subtrees = uniq_tree[nodes - root]
                
                # Multiply combinations and add to total for this tree size
                total += left_subtrees * right_subtrees
                
            uniq_tree[nodes] = total
        
        return uniq_tree[n]

Complexity

  • Time: $O(n^2)$
    Since we have two nested loops: the outer loop runs from 2 to n (which is $O(n)$), and the inner loop runs from 1 to nodes (which can also be up to $O(n)$). Therefore, the overall time complexity is $O(n^2)$.

  • Space: $O(n)$
    Since we are using an array uniq_tree of size n + 1 to store the number of unique BSTs for each number of nodes, the space complexity is $O(n)$.

Mistakes I Made

I had to look this up :(

And we are done.