Distinct BST Formations

MEDIUM30 pts

Given a positive integer n, determine the total count of structurally unique Binary Search Trees (BSTs) that can be constructed using exactly n nodes, where each node holds a distinct value from the sequence 1 through n.

A Binary Search Tree is a hierarchical data structure where for every node:

All values in the left subtree are strictly less than the node's value
All values in the right subtree are strictly greater than the node's value

Two BSTs are considered structurally different if they have distinct tree shapes, meaning the arrangement of parent-child relationships differs between them. Note that trees with the same structure but different node value assignments that still satisfy BST properties are counted as distinct structures based on which value serves as the root and how subtrees are organized.

Your task is to compute how many such unique tree configurations exist for the given value of n.

Example

Input

n = 3

Output

5

Explanation

With 3 nodes containing values [1, 2, 3], there are exactly 5 structurally unique BSTs:

Root=1, right child=2, right grandchild=3 (chain leaning right)
Root=1, right child=3, left grandchild=2
Root=2, left child=1, right child=3 (balanced tree)
Root=3, left child=1, right grandchild=2
Root=3, left child=2, left grandchild=1 (chain leaning left)

Each configuration represents a valid BST with a different tree shape.

Example

Input

n = 1

Output

1

Explanation

With only one node containing value 1, there is exactly one possible BST: a single root node with no children.

Example

Input

n = 2

Output

2

Explanation

With 2 nodes containing values [1, 2], there are exactly 2 structurally unique BSTs:

Root=1, right child=2
Root=2, left child=1

These represent the two possible ways to arrange 2 nodes in a BST.

Accepted0/0·0% Acceptance

Constraints

1 ≤ n ≤ 19

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

n =

Distinct BST Formations

Hints

Distinct BST Formations

Hints