1. Problem Summary
You are given an integer n. Consider all binary search trees (BSTs) that:
Have exactly n nodes.
Use each value from 1 to n exactly once.
Obey the BST property: for every node, left subtree values < node value < right subtree values.
Task: Return the number of structurally unique BSTs you can form (you do not need to generate the trees themselves).
Input: n (1 ≤ n ≤ 19)
Output: An integer: count of unique BST structures.
2. Examples Explanation
Example 1:
Input: n = 3
Output: 5
From problem 95, the 5 structures for values {1,2,3} are:
Root 1: right subtree formed from {2,3} (2 possibilities)
Root 2: left from {1}, right from {3} (1 possibility)
Root 3: left subtree formed from {1,2} (2 possibilities)
Total: 2 + 1 + 2 = 5.
Example 2:
Input: n = 1
Only one node with value 1, so exactly one BST.
Output: 1.
3. Approach
Pattern:
This is a classic Dynamic Programming / Catalan numbers problem on BST counting.
Key Idea: Choose Each Value as Root
Let:
G(n) = number of unique BSTs that store values 1..n.
Choose root as i (where 1≤i≤n):
Left subtree uses values 1..i-1 → number of ways: G(i-1).
Right subtree uses values i+1..n → number of ways: G(n-i) (same as size n-i).
For root i, total BSTs =
G(i-1) * G(n-i)
Summing over all possible roots i:
G(n) = Σ G(i-1) * G(n-i), i = 1 to n
Base cases:
G(0)=1 (empty tree is one valid structure in the combinatorial sense)
G(1)=1
This recurrence is exactly the Catalan number recurrence. We compute G[0..n] with DP.
High-Level DP Steps:
Create array dp of size n+1.
Initialize:
dp[0] = 1
dp[1] = 1
For nodes from 2 to n:
Set dp[nodes] = 0
For each root i from 1 to nodes:
dp[nodes] += dp[i-1] * dp[nodes-i]
Answer is dp[n].
Pseudo-code:
Complexity Analysis:
Time Complexity:
Two nested loops: nodes from 1..n, root from 1..nodes.
This is roughly O(n2).
Space Complexity:
DP array of size n+1.
O(n) extra space.
4. Java code
5. C code
6. C++ code
7. Python code
8. JavaScript code
Comments
Post a Comment