Unique Binary Search Trees
Posted: 23 Mar, 2021
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'.
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.
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.
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.