Unique Binary Search Trees - Video Solutions

Problem Overview: You need to count how many structurally unique binary search trees (BSTs) can be built using values 1..n. Every tree must follow the BST rule: left subtree values are smaller than the root and right subtree values are larger.

Approach 1: Dynamic Programming (O(n²) time, O(n) space)

The key observation: if you choose a number i as the root, all numbers 1..i-1 form the left subtree and i+1..n form the right subtree. The number of BSTs with root i equals the number of left subtree combinations multiplied by the number of right subtree combinations. Define dp[k] as the number of unique BSTs that can be built with k nodes. For each nodes from 1..n, iterate every possible root and accumulate dp[left] * dp[right]. This bottom-up dynamic programming approach avoids recomputing subtree counts and directly models the recursive structure of binary search trees. Time complexity is O(n²) due to the nested loops over nodes and root choices, while space complexity is O(n) for the DP array.

Approach 2: Catalan Number Formula (O(n) time, O(1) space)

The result of this problem follows the Catalan sequence, a well-known pattern in combinatorics. The number of unique BSTs with n nodes equals the nth Catalan number: C(n) = (2n)! / ((n + 1)! * n!). Instead of computing factorials directly, you can iteratively compute the value using the recurrence C(n+1) = C(n) * 2(2n+1)/(n+2). This avoids large factorial calculations and keeps the computation efficient. The approach comes from counting valid tree structures formed under combinatorial math constraints and works because each BST structure corresponds to a Catalan arrangement. Time complexity is O(n) with O(1) extra space.

Recommended for interviews: The dynamic programming solution is what most interviewers expect first. It demonstrates that you understand how BST structure splits into independent subproblems and how to model that with dynamic programming. After presenting the DP approach, mentioning that the result corresponds to the Catalan sequence shows deeper algorithmic knowledge. DP proves you can derive the recurrence from the problem itself, while the Catalan formula shows familiarity with classic counting patterns in tree problems.