/96. Unique Binary Search Trees

96. Unique Binary Search Trees

Medium
Probability63.4% acceptance

Given an integer node_count, compute and return the number of structurally unique binary search trees (BSTs) that can be constructed using node_count distinct values labeled from 1 to node_count.

Example 1

Input: node_count=4

Output: 14

Explanation: There are 14 structurally unique BSTs with 4 nodes.

Example 2

Input: node_count=2

Output: 2

Explanation: There are 2 structurally unique BSTs with 2 nodes.

Constraints

  • 1 <= node_count <= 19
Python (current runtime)

Case 1

Input: node_count=5

Expected: 42

Case 2

Input: node_count=6

Expected: 132

Case 3

Input: node_count=7

Expected: 429

Case 4

Input: node_count=8

Expected: 1430