{x}
blog image

Unique Binary Search Trees

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.

 

Example 1:

Input: n = 3
Output: 5

Example 2:

Input: n = 1
Output: 1

 

Constraints:

  • 1 <= n <= 19

Solution Explanation: Unique Binary Search Trees

This problem asks to find the number of structurally unique Binary Search Trees (BSTs) that can be formed with n nodes, where each node has a unique value from 1 to n. The solution presented uses dynamic programming for an efficient approach.

Approach: Dynamic Programming

The core idea is to break down the problem into smaller subproblems and build up the solution iteratively. We use a DP array f where f[i] represents the number of unique BSTs with i nodes.

  1. Base Case: f[0] = 1. A BST with 0 nodes is considered a valid empty BST.

  2. Recursive Relation: For a BST with i nodes, we consider each node from 1 to i as the root. If we choose node k as the root:

    • The left subtree will have k-1 nodes (nodes 1 to k-1). The number of unique BSTs for this subtree is f[k-1].
    • The right subtree will have i-k nodes (nodes k+1 to i). The number of unique BSTs for this subtree is f[i-k].
    • The total number of unique BSTs with k as the root is the product of the number of unique BSTs for the left and right subtrees: f[k-1] * f[i-k].

  3. Iteration: To calculate f[i], we sum the number of unique BSTs for each possible root node k (from 1 to i): f[i] = Σ (f[k-1] * f[i-k]) for k = 1 to i

Time and Space Complexity

  • Time Complexity: O(n2). The nested loops iterate through i from 1 to n and j from 0 to i-1, resulting in a quadratic time complexity.
  • Space Complexity: O(n). We use an array f of size n+1 to store the results of subproblems.

Code Explanation (Python)

class Solution:
    def numTrees(self, n: int) -> int:
        f = [1] + [0] * n  # Initialize DP array. f[0] = 1 (base case)
 
        for i in range(1, n + 1):  # Iterate through number of nodes
            for j in range(i):  # Iterate through possible root nodes
                f[i] += f[j] * f[i - j - 1]  # Apply recursive relation
 
        return f[n]  # Return the result for n nodes

The code in other languages (Java, C++, Go, TypeScript, Rust, C#) follows the same logic, differing only in syntax and data structure implementations. The core dynamic programming algorithm remains consistent across all the provided examples.