Unique Binary Search Trees Medium 0 attempts
LeetCode ↗

Unique Binary Search Trees

Medium TreeBinary TreeDFS LeetCode

Given n, return the number of structurally unique BSTs that store values 1 to n.

Example: n = 3 ā†’ Output: 5

Sample Input
ā€”
Sample Output
ā€”
Constraints
  • 1 <= n <= 19
Test Cases
Case 1
Args: [3] Expected: 5
Case 2
Args: [1] Expected: 1
Topics
TreeBinary TreeDFS

Catalan Number / DP

function numTrees(n) {
  const dp = Array(n+1).fill(0);
  dp[0] = dp[1] = 1;
  for (let i = 2; i <= n; i++)
    for (let j = 0; j < i; j++)
      dp[i] += dp[j] * dp[i-1-j];
  return dp[n];
}

Time: O(nĀ²) | Space: O(n)

Saved in this browser only. Private to you.

JavaScript