Unique Binary Search Trees - Video Solutions

Problem Overview: Given an integer n, count how many structurally unique binary search trees can be built using values from 1 to n. Each number must appear exactly once. Different tree shapes count as different BSTs even if they contain the same values.

Approach 1: Dynamic Programming (Time: O(n²), Space: O(n))

The key observation comes from the BST property: when you pick a value i as the root, all numbers 1..i-1 must form the left subtree and i+1..n must form the right subtree. The number of unique BSTs with i as root equals the number of possible left subtrees multiplied by the number of right subtrees. Define dp[k] as the number of BSTs that can be formed using k nodes. For each total node count k, iterate every node as root and accumulate dp[left] * dp[right]. This bottom-up dynamic programming approach builds answers from smaller subtree sizes.

Initialize dp[0] = 1 and dp[1] = 1 because an empty tree and a single-node tree both have exactly one valid structure. For each nodes from 2 to n, iterate possible roots and compute subtree combinations. The nested iteration leads to O(n²) time complexity. Space stays O(n) for the DP array.

Approach 2: Catalan Number Formula (Time: O(n), Space: O(1))

This problem is a direct application of the Catalan sequence, a classic result from math and combinatorics. The number of unique BSTs with n nodes equals the nth Catalan number. The closed-form formula is C(n) = (1 / (n + 1)) * binomial(2n, n). Instead of computing large factorials, you can iteratively calculate the binomial coefficient using multiplication and division to avoid overflow.

The Catalan interpretation works because every BST can be uniquely defined by choosing a root and recursively combining valid left and right subtree counts. This is exactly the recurrence used in the DP solution, but the mathematical formula collapses the recurrence into a direct computation. The iterative Catalan computation runs in O(n) time with constant extra space.

Recommended for interviews: Start with the Dynamic Programming approach. It demonstrates understanding of the BST root-partition idea and shows you can translate a recursive counting problem into a DP recurrence. Interviewers usually expect dp[n] = sum(dp[left] * dp[right]). Mentioning the Catalan number formula afterward signals deeper algorithm knowledge and familiarity with common combinatorial patterns.