Unique Binary Search Trees

The problem of Unique Binary Search Trees asks you to calculate the number of structurally unique Binary Search Trees (BSTs) that can be constructed from a sequence of distinct numbers. This is a classic dynamic programming problem with applications in understanding tree structures and combinatorial possibilities. Successfully solving this challenge demonstrates an understanding of recursion, dynamic programming, and tree properties.

Problem Description

Given an integer n, you need to determine the number of structurally unique BSTs that can be formed using integers from 1 to n. A BST is defined as a tree where the value of each node is greater than all values in its left subtree and less than all values in its right subtree. The order of nodes within the left and right subtrees does not matter, only the structure.

What needs to be achieved:

Calculate the number of unique BSTs possible for a given n.

Key requirements:

• The input will be a positive integer n.
• The BSTs must adhere to the BST property (left subtree < node < right subtree).
• The numbers used to construct the BSTs must be from 1 to n.
• The solution should be efficient, avoiding redundant calculations.

Expected behavior:

The function should return an integer representing the total number of unique BSTs.

Edge cases to consider:

• n = 0: There is one unique BST (an empty tree).
• n = 1: There is one unique BST (a single node).
• Larger values of n require efficient computation to avoid timeouts.

Examples

Example 1:

Input: 3
Output: 5
Explanation:
Given 3 nodes, the possible BSTs are:
   1     3     3     1     2
    \   /     /     \   /
     3   2     1     2
      /
     2

Example 2:

Input: 1
Output: 1
Explanation:
Only one BST can be formed with a single node.

Example 3:

Input: 0
Output: 1
Explanation:
An empty tree is considered a valid BST.

Constraints

• 0 <= n <= 19 (This constraint is important for preventing integer overflow and ensuring reasonable execution time. The number of BSTs grows very quickly.)
• The input n will always be an integer.
• The solution should ideally have a time complexity of O(n^2) or better.

Notes

This problem can be efficiently solved using dynamic programming. Consider how the number of BSTs for a given n can be derived from the number of BSTs for smaller values. Think about how each number from 1 to n can act as the root of a BST, and how this affects the sizes of the left and right subtrees. The Catalan numbers are closely related to this problem. A recursive approach without memoization will likely result in timeouts for larger values of n.

Pseudocode:

function numTrees(n):
  // Create a DP table to store the number of unique BSTs for each size
  dp = array of size (n + 1) initialized with 0

  // Base cases
  dp[0] = 1  // Empty tree
  dp[1] = 1  // Single node

  // Iterate from 2 to n
  for i from 2 to n:
    // For each possible root value 'j' from 1 to i
    for j from 1 to i:
      // The number of BSTs with 'j' as the root is the product of
      // the number of BSTs in the left subtree (size j-1) and
      // the number of BSTs in the right subtree (size i-j)
      dp[i] = dp[i] + (dp[j - 1] * dp[i - j])

  // Return the number of unique BSTs for size n
  return dp[n]