New update is available. Click here to update.

Unique Binary Search Trees

Posted: 23 Mar, 2021
Difficulty: Moderate


Try Problem

You are given an integer ‘N’, your task is to return the number of structurally unique BST's (binary search trees) which have exactly 'N' nodes of unique values from 1 to 'N'.

For example:

Given  ‘N’ = 2, The total number of BST’s is 2.


1. A binary search tree is a rooted binary tree whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree.

2. A structurally unique binary search tree is a tree that has at least 1 node at a different position or with a different value compared to another binary search tree.

Input format:

The first line of input contains an integer T denoting the number of test cases.

The first and the only line of each test case contains an integer 'N', the number of ‘nodes’.

Output format :

For each test case, print a single line containing a single integer denoting the total number of BST’s that can be formed. The output of each test case will be printed in a different line.

The output of each test case will be printed in a separate line.

Note :

You don't have to print anything. It's been already taken care of. Just implement the given function.


1 <= T <= 25
1 <= N <= 30

Where ‘T’ is the total number of test cases, and N is the number of nodes.

Time limit: 1 sec.