Medium

Unique Binary Search Trees II

LAB

Return the number of structurally unique BSTs storing values 1 through n.

EXAMPLES

Example 1

Input
{
  "n": 3
}

Output
5

FUNCTION SHAPE

n: int→int

SOLUTION NOTE

For each root, generate all left/right subtree combinations and connect them.

Reveal reference solution +

pythonREFERENCE

def generateTrees(self, n: int) -> List[TreeNode]:
    @cache
    def build(lo, hi):
        if lo > hi:
            return [None]

        result = []
        for root_val in range(lo, hi + 1):
            for left in build(lo, root_val - 1):
                for right in build(root_val + 1, hi):
                    root = TreeNode(root_val)
                    root.left = left
                    root.right = right
                    result.append(root)
        return result

    return build(1, n)

TimeO(4^n / n^1.5)

SpaceO(4^n / n^1.5)

Open on LeetCode ↗