Problem Statement in English

You’re given an integer n. Your task is to generate all structurally unique Binary Search Trees (BSTs) that store values 1 to n.

Approach

The fundamental breakdown of this problem is that we can recursively generate subtrees, and reuse them.

The way we generate subtrees is by rdescribing each subtree as operating in a certain range of values. Recall that a BST is a binary tree where for each node, all values in the left subtree are less than the node’s value, and all values in the right subtree are greater than the node’s value.

Once we generate all possible left and right subtrees by ranging the left subtree from the start of the current value to the end of the current value (exclusive), and the right subtree from the start of the current value to the end of the current value (exclusive), we can combine them using a nested loop with the current node to generate all unique trees.

And we’re done!

Solution in Python


class Solution:
    def generateTrees(self, n: int) -> list[TreeNode | None]:
        @cache
        def dfs(start, end):
            if start > end:
                return [None]
                
            res = []

            for i in range(start, end + 1):
                left_trees = dfs(start, i - 1)
                right_trees = dfs(i + 1, end)

                for left in left_trees:
                    for right in right_trees:
                        res.append(TreeNode(i, left, right))

            return res

        return dfs(1, n)

Complexity

  • Time: $O(4^n)$
    This is not the most precise calculation, since for a precise calculation you need to know about Catalan numbers, and that kind of thing is not what I want us to have to know.

    The way one can think about is that there are exactly $n$ nodes that have a value, and $n + 1$ positions that do not have a value, and a total of $2n + 1$ positions.

      graph TD
      A((2)) --> B((1))
      A --> C((3))
      B -.-> D["None"]
      B -.-> E["None"]
      C -.-> F["None"]
      C -.-> G["None"]

    Now, recall the binomial theorem (don’t worry, I didn’t recall it, I got it from chatgpt hehe 😁):

    $$\sum_{k=0}^{m}\binom{m}{k}=2^m$$

    Here $m$ and $k$ are $2n + 1$ and $n$, respectively.

    Plugging this back into the equation, we get:

    $$\sum_{k=0}^{2n + 1}\binom{2n + 1}{k}=2^{2n + 1}$$

    And here we see that the term $4^n$ dominates, and thus we can say that the time complexity is $O(4^n)$.

  • Space: $O(4^n)$
    Since there are $O(4^n)$ trees, and we’re storing atleast those many roots (since the subtrees may be reused), we can say that the space complexity is $O(4^n)$.

Mistakes I Made

I couldn’t figure out how to try all combos of left and right subtrees and never thought of just using a nested loop 🤦‍♂️

I also struggled with calculating the time and space complexity of this.

And we are done.