Unique Binary Search Trees Medium 0 attempts
LeetCode ↗

Unique Binary Search Trees

Medium TreeBinary TreeDFS LeetCode

For a given integer n, count how many distinct binary search tree shapes can be built using exactly the keys 1 through n (a BST being a tree where every node's left subtree holds smaller values and its right subtree holds larger ones).

Input Format
Implement numTrees(n). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
n = 3
Output
5

Example 2

Input
n = 1
Output
1
Constraints
  • 1 <= n <= 19
Test Cases (2)
Case 1
Args: [3] Expected: 5
Case 2
Args: [1] Expected: 1
Topics
TreeBinary TreeDFS

Catalan Number / DP

javascript
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