Hide sidebar
leetcode/DSA courseSystem Design

Unique Binary Search Trees

TreesDynamic Programming
MediumLeetCode #96

Problem Statement

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

Example 1

Input: n = 3

Output: 5

Example 2

Input: n = 1

Output: 1

Algorithm Explanation

This problem can be solved using dynamic programming. The number of unique BSTs for `n` nodes is related to the Catalan numbers. Let `G(n)` be the number of unique BSTs for `n` nodes.

Algorithm Steps

  • Base Cases: For `n = 0`, there is one unique BST (the empty tree), so `G(0) = 1`. For `n = 1`, there is one unique BST (a single node), so `G(1) = 1`.
  • Subproblems: For a given `n`, we can choose any number `i` from `1` to `n` as the root. If we choose `i` as the root, then `1, ..., i-1` must be in the left subtree, and `i+1, ..., n` must be in the right subtree.
  • Recurrence Relation: The number of unique BSTs with `i` as the root is `G(i-1) * G(n-i)`. We sum this up for all possible roots `i` from `1` to `n`. So, `G(n) = sum(G(i-1) * G(n-i))` for `i` from `1` to `n`.
  • DP Table: We can use a DP table to store the results for `G(0), G(1), ..., G(n)`. We build this table up from the base cases.
Initialization
Base cases: dp[0] = 1, dp[1] = 1
1
dp[0]
1
dp[1]
0
dp[2]
0
dp[3]
0
dp[4]
0
dp[5]
Unique BSTs Solution

class Solution:
    def numTrees(self, n: int) -> int:
        # G[i] will store the number of unique BST's for i nodes
        G = [0] * (n + 1)
        # Base cases
        G[0] = 1
        G[1] = 1

        # Fill the DP table
        for i in range(2, n + 1):
            for j in range(1, i + 1):
                # For each root j, the number of unique BSTs is the product of
                # unique BSTs in the left subtree (j-1 nodes) and
                # unique BSTs in the right subtree (i-j nodes)
                G[i] += G[j - 1] * G[i - j]
        
        return G[n]