Problem Description

You are given an integer n. Your task is to find how many structurally unique Binary Search Trees (BSTs) can be formed using exactly n nodes, where each node contains a unique value from 1 to n.

A Binary Search Tree is a tree data structure where:

• Each node has at most two children (left and right)
• For any node, all values in its left subtree are less than the node's value
• For any node, all values in its right subtree are greater than the node's value

Two BSTs are considered structurally different if they have different shapes, even if they might contain the same values in different positions.

For example:

• When n = 3, you can form 5 different BST structures using values 1, 2, and 3
• When n = 1, there's only 1 possible BST structure

The problem asks you to count the total number of such unique BST structures possible with n nodes containing values from 1 to n.

Intuition

To understand how to count unique BST structures, let's think about how BSTs are formed. When we pick a root node, all smaller values must go to the left subtree, and all larger values must go to the right subtree.

Consider we have values from 1 to n. If we choose value i as the root:

• Values 1 to i-1 must form the left subtree
• Values i+1 to n must form the right subtree

Here's the key insight: the number of unique structures for the left subtree depends only on how many nodes it has, not on the actual values. Whether we're arranging [1,2,3] or [5,6,7], the number of possible BST structures is the same - it only depends on having 3 nodes.

This means if we know how many unique BSTs can be formed with j nodes (left subtree) and how many can be formed with k nodes (right subtree), we can multiply these counts to get all possible combinations when node i is the root.

For example, with n=3:

• Root = 1: left has 0 nodes, right has 2 nodes
• Root = 2: left has 1 node, right has 1 node
• Root = 3: left has 2 nodes, right has 0 nodes

For each choice of root, we multiply the number of possible left subtree structures by the number of possible right subtree structures.

This naturally leads to a dynamic programming approach where f[i] represents the number of unique BSTs with i nodes. We can build up from smaller subproblems: f[i] = sum of (f[j] * f[i-j-1]) for all valid splits, where j is the size of the left subtree and i-j-1 is the size of the right subtree (accounting for the root node).

Learn more about Tree, Binary Search Tree, Math, Dynamic Programming and Binary Tree patterns.

Solution Approach

We implement the solution using dynamic programming with a bottom-up approach. Let's define f[i] as the number of unique BSTs that can be formed with i nodes.

Base Case:

• f[0] = 1 - There's exactly one way to form an empty tree (no nodes)
• Initialize all other values to 0

State Transition: For each number of nodes i from 1 to n, we calculate f[i] by considering all possible root positions:

f[i] = sum of (f[j] * f[i-j-1]) for j from 0 to i-1

Where:

• j represents the number of nodes in the left subtree
• i-j-1 represents the number of nodes in the right subtree (we subtract 1 for the root)
• f[j] * f[i-j-1] gives us all combinations for this specific split

Implementation Steps:

1. Create an array f of size n+1 initialized with f[0] = 1 and rest as 0

2. For each i from 1 to n:

   • For each possible left subtree size j from 0 to i-1:
     • Add f[j] * f[i-j-1] to f[i]
     • This accounts for all BSTs where the left subtree has j nodes

3. Return f[n] as the final answer

Example Walkthrough for n=3:

• f[0] = 1 (base case)
• f[1] = f[0] * f[0] = 1 * 1 = 1
• f[2] = f[0] * f[1] + f[1] * f[0] = 1*1 + 1*1 = 2
• f[3] = f[0] * f[2] + f[1] * f[1] + f[2] * f[0] = 1*2 + 1*1 + 2*1 = 5

The time complexity is O(n²) as we have two nested loops, and the space complexity is O(n) for the DP array.

Example Walkthrough

Let's walk through the solution for n = 4 to see how we count unique BST structures.

Step 1: Initialize DP array

• Create array f where f[i] = number of unique BSTs with i nodes
• f[0] = 1 (empty tree), rest initialized to 0
• f = [1, 0, 0, 0, 0]

Step 2: Calculate f[1]

• With 1 node, we can only make one tree
• When root is chosen: left has 0 nodes, right has 0 nodes
• f[1] = f[0] × f[0] = 1 × 1 = 1
• f = [1, 1, 0, 0, 0]

Step 3: Calculate f[2]

• With 2 nodes (values 1,2), consider each as root:
  • Root = 1: left has 0 nodes, right has 1 node → f[0] × f[1] = 1 × 1 = 1
  • Root = 2: left has 1 node, right has 0 nodes → f[1] × f[0] = 1 × 1 = 1
• f[2] = 1 + 1 = 2
• f = [1, 1, 2, 0, 0]

Step 4: Calculate f[3]

• With 3 nodes (values 1,2,3), consider each as root:
  • Root = 1: left has 0 nodes, right has 2 nodes → f[0] × f[2] = 1 × 2 = 2
  • Root = 2: left has 1 node, right has 1 node → f[1] × f[1] = 1 × 1 = 1
  • Root = 3: left has 2 nodes, right has 0 nodes → f[2] × f[0] = 2 × 1 = 2
• f[3] = 2 + 1 + 2 = 5
• f = [1, 1, 2, 5, 0]

Step 5: Calculate f[4]

• With 4 nodes (values 1,2,3,4), consider each as root:
  • Root = 1: left has 0 nodes, right has 3 nodes → f[0] × f[3] = 1 × 5 = 5
  • Root = 2: left has 1 node, right has 2 nodes → f[1] × f[2] = 1 × 2 = 2
  • Root = 3: left has 2 nodes, right has 1 node → f[2] × f[1] = 2 × 1 = 2
  • Root = 4: left has 3 nodes, right has 0 nodes → f[3] × f[0] = 5 × 1 = 5
• f[4] = 5 + 2 + 2 + 5 = 14

Final Answer: 14 unique BST structures can be formed with 4 nodes

The key insight is that for each possible root position, we multiply the number of ways to arrange the left subtree by the number of ways to arrange the right subtree. This works because the structural uniqueness depends only on the count of nodes in each subtree, not their actual values.

Solution Implementation

Time and Space Complexity

The time complexity is O(n²), not O(n) as stated in the reference answer. The code uses two nested loops - the outer loop runs from 0 to n (n+1 iterations), and for each iteration i, the inner loop runs from 0 to i-1 (i iterations). The total number of operations is approximately 1 + 2 + 3 + ... + n = n(n+1)/2, which gives us O(n²) time complexity.

The space complexity is O(n). The code creates an array f of size n+1 to store the intermediate results for dynamic programming, requiring linear space proportional to the input size n.

Note: The reference answer appears to be incorrect regarding the time complexity. This algorithm computes Catalan numbers using dynamic programming, and the nested loop structure inherently results in quadratic time complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Base Case Initialization

A common mistake is forgetting to initialize dp[0] = 1 or incorrectly setting it to 0. This breaks the entire calculation since an empty tree (0 nodes) is a valid structure that should count as 1 possibility.

Wrong approach:

dp = [0] * (n + 1)  # Missing dp[0] = 1

Correct approach:

dp = [1] + [0] * n  # Properly initialize dp[0] = 1

2. Off-by-One Errors in Loop Indices

The inner loop logic can be confusing. A frequent error is miscalculating the indices for left and right subtree sizes, especially when translating between "root position" and "subtree size".

Wrong approach:

for root_position in range(num_nodes):  # Should be 1 to num_nodes+1
    left = dp[root_position]
    right = dp[num_nodes - root_position - 1]

Correct approach:

for root_position in range(1, num_nodes + 1):
    left = dp[root_position - 1]
    right = dp[num_nodes - root_position]

3. Integer Overflow in Other Languages

While Python handles large integers automatically, in languages like Java or C++, the result can overflow for larger values of n. The Catalan numbers grow exponentially, and even for n=19, the result exceeds 32-bit integer limits.

Solution for other languages:

• Use long or long long data types
• In Java: long[] dp = new long[n + 1];
• In C++: vector<long long> dp(n + 1);

4. Misunderstanding the Problem - Counting Values vs. Structures

Some might think the problem asks for different value arrangements rather than different tree structures. Remember: we're counting structurally unique trees, not different ways to arrange values 1 to n in those structures.

Key insight: For a given structure, there's only one valid way to place values 1 to n to make it a BST. The problem counts structures, not value permutations.