Definition
- Structurally Unique BSTs – generate every distinct binary search tree that stores values 1 through N.
- Divide and conquer – for each value as root, smaller values form the left subtree, larger values the right subtree.
- Recursive pairing – generate all left shapes and all right shapes, then create a tree for each (left, right) combination under the chosen root.
- Empty-range sentinel – returning a list with one null for an empty range lets pairing loops run correctly when a subtree is absent.
- Catalan number – the count of unique BST shapes for N values is C(N) = (2N)! / ((N+1)! * N!), which grows exponentially.
At the National Bank of India, an interest-tier lookup can be organized as a search tree over tier numbers 1 to N. Different tree shapes give different lookup depths. Analytics wants every valid shape to benchmark performance. Rajesh picks each tier as root, builds all shapes for the lower tiers on the left and higher tiers on the right, and combines them.
Understanding the Concepts
What is the Structurally Unique BSTs problem?
Given an integer N, generate all structurally unique BSTs that store the values 1 through N. Each tree must satisfy the BST ordering invariant: for every node, all values in the left subtree are smaller and all values in the right subtree are larger.
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
public class UniqueBSTs {
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
public static List<TreeNode> generateTrees(int n) {
if (n == 0) return new ArrayList<>();
return generate(1, n);
}
private static List<TreeNode> generate(int start, int end) {
List<TreeNode> result = new ArrayList<>();
if (start > end) {
result.add(null); // empty subtree sentinel
return result;
}
for (int i = start; i <= end; i++) {
List<TreeNode> leftTrees = generate(start, i - 1);
List<TreeNode> rightTrees = generate(i + 1, end);
for (TreeNode left : leftTrees) {
for (TreeNode right : rightTrees) {
TreeNode root = new TreeNode(i);
root.left = left;
root.right = right;
result.add(root);
}
}
}
return result;
}
public static void main(String[] args) {
List<TreeNode> trees = generateTrees(3);
System.out.println("Number of unique BSTs for N=3: " + trees.size());
}
}
Number of unique BSTs for N=3: 5
Why does the BST ordering property drive the recursion?
When you choose value i as the root, the BST invariant forces all values less than i into the left subtree and all values greater than i into the right subtree. This splits the range [start, end] into [start, i-1] and [i+1, end], which is a natural divide-and-conquer.
// Choosing root i from [1, 3]:
// i=1: left=[], right=[2,3]
// i=2: left=[1], right=[3]
// i=3: left=[1,2], right=[]
// For i=2:
// Left subtrees of [1]: just {1}
// Right subtrees of [3]: just {3}
// Pairing: one tree with root=2, left=1, right=3
Why is the empty-range sentinel critical?
When start > end, the range is empty, meaning no subtree exists. Returning a list with one null lets the pairing loops execute once even when a subtree is absent. Without this, the pairing loop would produce zero trees when one side is empty, losing valid trees where the root has only one child.
// WRONG: returning empty list for empty range
if (start > end) return new ArrayList<>(); // empty list
// Pairing: for (left in []) for (right in [...]) -> nothing produced!
// We lose all trees where this side has no child
// CORRECT: return list with one null
if (start > end) {
result.add(null); // sentinel for absent subtree
return result;
}
// Pairing: for (left in [null]) for (right in [...]) -> correct trees produced
How many unique BSTs are there?
The number of unique BST shapes for N values is the Nth Catalan number: C(N) = (2N)! / ((N+1)! * N!). This grows exponentially, so generation is practical only for small N.
package com.bank.service;
public class CatalanNumber {
public static int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = 1; dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 0; j < i; j++) {
dp[i] += dp[j] * dp[i - 1 - j];
}
}
return dp[n];
}
public static void main(String[] args) {
for (int n = 1; n <= 8; n++) {
System.out.println("N=" + n + ": " + numTrees(n) + " unique BSTs");
}
}
}
N=1: 1 unique BSTs
N=2: 2 unique BSTs
N=3: 5 unique BSTs
N=4: 14 unique BSTs
N=5: 42 unique BSTs
N=6: 132 unique BSTs
N=7: 429 unique BSTs
N=8: 1430 unique BSTs
How is counting different from generation?
Counting uses dynamic programming: dp[i] = sum of dp[j] * dp[i-1-j] for j in [0, i-1]. This runs in O(n^2) time and O(n) space. Generation must build actual tree nodes, which takes O(C(n) * n) time and space because each of the C(n) trees has n nodes.
| Aspect | Counting (numTrees) | Generation (generateTrees) |
|---|---|---|
| Result | Single integer | List of tree roots |
| Time | O(n^2) | O(C(n) * n) |
| Space | O(n) | O(C(n) * n) for tree nodes |
| Memoization | Straightforward | Memoizes lists of roots per range |
// Counting: dp table, O(n^2)
// dp[3] = dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0] = 2+1+2 = 5
// Generation: actual tree construction
// For N=3: build 5 distinct TreeNode trees
What are the edge cases?
N=0 returns an empty list (no trees). N=1 returns a single tree with just the root. The null sentinel handles all one-child cases internally.
package com.bank.service;
public class UniqueBSTsEdge {
public static void main(String[] args) {
System.out.println("N=0: " + UniqueBSTs.generateTrees(0).size()); // 0
System.out.println("N=1: " + UniqueBSTs.generateTrees(1).size()); // 1
System.out.println("N=2: " + UniqueBSTs.generateTrees(2).size()); // 2
}
}
N=0: 0
N=1: 1
N=2: 2
What are common mistakes?
The most common mistake is returning an empty list instead of a list with null for the empty range. This causes the pairing loop to produce nothing when one side is absent.
// WRONG:
if (start > end) return new ArrayList<>();
// Result: trees with one-child roots are never generated
// CORRECT:
if (start > end) { result.add(null); return result; }
When should you use this technique?
Use this divide-and-conquer approach when you need to enumerate all valid tree structures. In banking, it applies to benchmarking lookup trees for interest-tier configurations.
package com.bank.service;
public class TierBenchmark {
public static void main(String[] args) {
int tiers = 5;
var trees = UniqueBSTs.generateTrees(tiers);
System.out.println("Unique tier-lookup trees for " + tiers + " tiers: " + trees.size());
}
}
Unique tier-lookup trees for 5 tiers: 42
What should a senior engineer know?
A senior engineer should explain the Catalan number formula, the difference between counting and generation, and why the empty-range sentinel is essential for correctness. They should also note that generation is exponential and only practical for small N.
What are common interview follow-up questions?
- Interviewers commonly ask:
- How many unique BSTs for N values? (Catalan number.)
- Can you just count without generating? (Yes, DP in O(n^2).)
- Why return [null] for empty range? (Pairing loop needs to execute once.)
- What is the time complexity of generation? (O(C(n) * n), exponential.)
Visual Overview
Generating unique BSTs for N=3:
Choose root = 1:
left = [] right = [2,3]
left shapes: [null] right shapes: 2 trees
Trees: 1 1
\ \
2 3
\ /
3 2
Choose root = 2:
left = [1] right = [3]
left shapes: 1 tree right shapes: 1 tree
Tree: 2
/ \
1 3
Choose root = 3:
left = [1,2] right = []
left shapes: 2 trees right shapes: [null]
Trees: 3 3
/ /
1 2
\ /
2 1
Total: 2 + 1 + 2 = 5 = Catalan(3)
Key Takeaway
Generating all structurally unique BSTs for values 1 through N uses divide and conquer driven by the BST ordering invariant. For each value chosen as root, everything smaller goes left and everything larger goes right. You recursively generate every possible left shape and right shape, then pair each combination under the root to form complete trees.
The empty-range sentinel is the detail that makes the recursion correct. When a range is empty, returning a list with one null (not an empty list) ensures the pairing loop executes once and correctly produces trees where the root has only one child. Without this, those trees are silently lost.
The count of unique BST shapes is the Catalan number, which grows exponentially. Counting alone uses DP in O(n^2), but generation must construct all C(n)*n tree nodes, so it is practical only for small N.
At the National Bank of India, the analytics team benchmarks interest-tier lookup trees. Tiers 1 through N can be arranged in many valid BST shapes, and each shape gives different worst-case and average lookup depths. Generating all shapes for small tier counts lets the team pick the one with the best average depth, and the Catalan count tells them how many shapes to expect.
Remember one sentence: make each value the root, recurse for left and right shapes, pair them, and return [null] for empty ranges so one-child trees are not lost.
---