#96

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Unique Binary Search Trees

Given n nodes, calculate the number of unique binary search trees (BSTs) that can be formed with values from 1 to n.

math dynamic programming tree binary search tree binary tree

Problem Statement

Given an integer n, return the number of structurally unique binary search trees (BSTs) that can be formed using the integers from 1 to n. The BSTs must be formed such that each node has a unique value, and they satisfy the properties of a binary search tree.

For example, when n = 3, there are 5 possible unique BSTs, and when n = 1, the only tree that can be formed is a single node. Your goal is to find an efficient way to compute this for any given n between 1 and 19.

Examples

Example 1

Input: n = 3

Output: 5

Example details omitted.

Example 2

Input: n = 1

Output: 1

Example details omitted.

Constraints

1 <= n <= 19

Solution Approach

Dynamic Programming with Catalan Numbers

This problem can be solved using dynamic programming where we calculate the number of unique BSTs for each value of n starting from 0 up to n. The number of BSTs for a given n is given by the recursive relation: G(n) = sum(G(i) * G(n-i-1)) for i in [0, n-1]. This uses the fact that each node can serve as a root, and the left and right subtrees are independent.

Binary Tree Traversal with Memoization

Using binary tree traversal, we can solve this problem by memoizing the results of each subtree configuration. For each node, we consider all the nodes before it as the left subtree and those after it as the right subtree. The results of these subtrees are stored, avoiding redundant calculations and ensuring optimal performance.

Mathematical Formula for Catalan Numbers

The problem is also related to the Catalan number sequence, where the nth Catalan number gives the number of distinct binary search trees with n nodes. The formula for the nth Catalan number is: C(n) = (2n)! / ((n+1)! * n!). This formula can be used to compute the number of unique BSTs directly for small values of n.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexity depend on the final approach. Using dynamic programming, the time complexity is O(n^2), and the space complexity is O(n). The memoized binary-tree traversal can have a time complexity of O(n) and space complexity of O(n). The Catalan number formula can compute the result in O(1) time but involves factorials, so practical limits are set by the factorial computations.

What Interviewers Usually Probe

Do you understand how dynamic programming can be applied to this problem?
Can you explain why the solution involves recursive subproblems?
Will you be able to efficiently calculate the Catalan number using a mathematical formula?

Common Pitfalls or Variants

Common pitfalls

Not memoizing the results of subproblems, leading to redundant calculations.
Incorrectly assuming that the solution can be computed in linear time without considering the complexity of recursive calls.
Failing to realize that the number of BSTs grows exponentially, which may lead to inefficiencies in time complexity if not optimized.

Follow-up variants

How would the problem change if we allowed duplicate values in the BST?
What happens if the BST formation is restricted by some additional constraints, like balanced height?
How can this approach be adapted to count the number of unique AVL trees instead of BSTs?

FAQ

What is the pattern used to solve Unique Binary Search Trees?

The problem is solved using dynamic programming, where each subproblem represents the number of BSTs that can be formed with a subset of nodes. The result is built iteratively based on smaller subtrees.

How can we optimize the solution for large n in Unique Binary Search Trees?

To optimize, we can use memoization to store the results of previously computed subproblems, preventing redundant calculations. Additionally, the Catalan number formula can be used for direct computation in some cases.

What is the time complexity of the dynamic programming approach?

The time complexity of the dynamic programming approach is O(n^2) due to the nested loops required to compute the number of BSTs for each node. Space complexity is O(n).

How does the recursive formula for Unique Binary Search Trees work?

The recursive formula for the number of unique BSTs is G(n) = sum(G(i) * G(n-i-1)) for i in [0, n-1], where each node is considered as the root, and its left and right subtrees are computed independently.

Can the number of unique BSTs be computed using Catalan numbers?

Yes, the number of unique BSTs corresponds to the nth Catalan number, which can be computed directly using the formula C(n) = (2n)! / ((n+1)! * n!).

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i]$ to represent the number of binary search trees that can be generated from $[1, i]$. Initially, $f[0] = 1$, and the answer is $f[n]$.

1

2

3

4

5

6

7

class Solution:
    def numTrees(self, n: int) -> int:
        f = [1] + [0] * n
        for i in range(n + 1):
            for j in range(i):
                f[i] += f[j] * f[i - j - 1]
        return f[n]

Continue Practicing

#95 unique binary search trees ii #1569 number of ways to reorder array to get same bst #98 validate binary search tree