Unique Binary Search Trees

Unique Binary Search Trees

What is this problem about?

The Unique Binary Search Trees interview question is a classic combinatorics and dynamic programming problem. Given an integer n, you need to calculate the total number of structurally unique Binary Search Trees (BSTs) that can be formed using nodes containing values from 1 to n. It’s not about building the trees, but simply counting how many different shapes are possible.

Why is this asked in interviews?

This problem is a staple at companies like Adobe, Microsoft, and Amazon because it tests a candidate's grasp of recursive structures. It requires understanding that a BST's structure is defined by its root; once a root is chosen, the values smaller than the root form the left subtree and the larger values form the right subtree. This realization is key to many advanced Tree interview patterns.

Algorithmic pattern used

The core Math, Binary Search Tree, Dynamic Programming interview pattern here is related to Catalan Numbers. We can solve this using DP: G(n) is the number of unique BSTs with n nodes. To calculate G(n), we sum the possibilities for each number i acting as the root. If i is the root, there are i-1 nodes in the left subtree and n-i nodes in the right subtree. The number of combinations for a fixed root i is G(i-1) * G(n-i).

Example explanation

For n = 3:

1. If 1 is the root: 0 nodes left, 2 nodes right. $G(0)*G(2) = 1*2 = 2$.
2. If 2 is the root: 1 node left, 1 node right. $G(1)*G(1) = 1*1 = 1$.
3. If 3 is the root: 2 nodes left, 0 nodes right. $G(2)*G(0) = 2*1 = 2$. Total: $2 + 1 + 2 = 5$ unique BSTs.

Common mistakes candidates make

Many candidates struggle to find the recursive relationship and try to draw every possible tree. Others forget the base cases ($G(0)=1$ and $G(1)=1$). Another mistake is not realizing that the values don't matter for the structure; only the number of nodes in the left and right subtrees determines the count.

Interview preparation tip

Get comfortable with Dynamic Programming on Trees. Problems that ask for "how many ways" often involve breaking the structure into independent sub-problems (like left and right subtrees) and multiplying their results.