Unique Binary Search Trees II

Unique Binary Search Trees II

What is this problem about?

While the first version asked for the count, the Unique Binary Search Trees II interview question asks you to actually generate all the structurally unique BSTs. For a given n, you must return a list of the root nodes of every possible BST that can be constructed with values from 1 to n.

Why is this asked in interviews?

Companies like Meta and Google use the Unique Binary Search Trees II coding problem to see if a candidate can implement complex recursive algorithms. Generating objects is harder than counting them because it requires careful memory management and an understanding of how to build and combine recursive structures. It’s an excellent test of your Backtracking and Tree skills.

Algorithmic pattern used

The Binary Search Tree, Backtracking, Tree interview pattern for this involves a recursive function generate(start, end). This function generates all possible BSTs using values in the range [start, end]. It iterates through each value i in the range, treating i as the root. It then recursively calls generate(start, i-1) to get all left subtrees and generate(i+1, end) to get all right subtrees. Finally, it loops through all combinations of left and right subtrees to create new trees with i as the root.

Example explanation

For n = 2:

1. generate(1, 2):
2. Try i = 1 as root:
   • Left subtrees from generate(1, 0): [null]
   • Right subtrees from generate(2, 2): [Node(2)]
   • Resulting tree: 1 -> (null, 2)
3. Try i = 2 as root:
   • Left subtrees from generate(1, 1): [Node(1)]
   • Right subtrees from generate(3, 2): [null]
   • Resulting tree: 2 -> (1, null)
4. The function returns a list containing these two tree roots.

Common mistakes candidates make

Handling the null base cases incorrectly is the most frequent error. If a range is invalid (start > end), the function should return a list containing null (not an empty list), so that the nested loops for combining subtrees can still execute. Another mistake is trying to use a global variable to track trees instead of returning them through the recursive calls.

Interview preparation tip

Practice Backtracking problems where you are building a structure. The key is to ensure that each recursive call returns a complete set of sub-components that the parent call can then assemble. This "bottom-up" construction is a vital skill for tree and graph problems.