Unique Binary Search Trees - Practice Coding Problems

Unique Binary Search Trees - Problem

Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.

A Binary Search Tree (BST) is a tree where for each node:

All values in the left subtree are less than the node's value
All values in the right subtree are greater than the node's value

Structurally unique means trees with different shapes, even if they contain the same values in different arrangements.

Input & Output

Example 1 — Small Case

$ Input: n = 3

› Output: 5

💡 Note: With 3 nodes (1,2,3), we can form 5 structurally unique BSTs: root=1 gives 2 trees, root=2 gives 1 tree, root=3 gives 2 trees. Total: 2+1+2=5

Example 2 — Base Case

$ Input: n = 1

› Output: 1

💡 Note: With only 1 node, there's exactly 1 way to form a BST - just a single node tree

Example 3 — Two Nodes

$ Input: n = 2

› Output: 2

💡 Note: With 2 nodes (1,2), we can form 2 BSTs: root=1 with right child 2, or root=2 with left child 1

Constraints

1 ≤ n ≤ 19

Visualization

Tap to expand

Understanding the Visualization

Input

Given n=3, need to count BSTs with nodes 1,2,3

Process

Try each node as root, count left×right combinations

Output

Sum all possibilities to get total count

Key Takeaway

🎯 Key Insight: Each root choice splits nodes into left and right subtrees, and we multiply the counts of possible subtree arrangements

Asked in

G Google 45 a Amazon 38 f Facebook 32 M Microsoft 28

The key insight is recognizing that BST counts follow Catalan numbers. For each root choice, we multiply the counts of possible left and right subtrees. Best approach uses dynamic programming or direct Catalan formula. Time: O(n), Space: O(1) with math approach.

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming	O(n²)	O(n)	Build up the solution using bottom-up DP, computing counts from 0 to n
Memoized Recursion	O(n²)	O(n)	Use memoization to cache results of subproblems and avoid redundant calculations
Catalan Numbers Formula	O(n)	O(1)	Use the mathematical fact that BST counts follow Catalan numbers sequence
Recursive Brute Force	O(4ⁿ)	O(n)	Recursively try each number as root and count all possible BST structures

Dynamic Programming — Algorithm Steps

Initialize DP array where dp[i] = count of BSTs with i nodes
Set base cases: dp[0] = dp[1] = 1
For each i from 2 to n, compute dp[i] using all possible roots
Return dp[n] as the final answer

Visualization

Tap to expand

Step-by-Step Walkthrough

Base Cases

Initialize dp[0]=1, dp[1]=1

Build Up

Compute each dp[i] using smaller values

Final Answer

Return dp[n]

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

int solution(int n) {
    // dp[i] represents number of unique BSTs with i nodes
    int* dp = (int*)calloc(n + 1, sizeof(int));
    
    // Base cases
    dp[0] = 1; // Empty tree
    if (n >= 1) dp[1] = 1; // Single node tree
    
    // Fill dp table for 2 to n nodes
    for (int nodes = 2; nodes <= n; nodes++) {
        for (int root = 1; root <= nodes; root++) {
            int leftNodes = root - 1;
            int rightNodes = nodes - root;
            dp[nodes] += dp[leftNodes] * dp[rightNodes];
        }
    }
    
    int result = dp[n];
    free(dp);
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int result = solution(n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Outer loop runs n times, inner loop runs up to n times for each iteration

⚠ Quadratic Growth

Space Complexity

O(n)

DP array stores counts for n+1 values from 0 to n

⚡ Linearithmic Space

230.6K Views

Medium Frequency

~15 min Avg. Time

8.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler