In this post, we will solve **Number of Binary Search Tree HackerRank Solution**. This problem** (Number of Binary Search Tree)** is a part of **HackerRank Functional Programming** series.

**Task**

A binary tree is a tree which is characterized by any of the following properties:

- It can be empty (null).
- It can contain a root node which contain some value and two subtree, left subtree and right subtree, which are also binary tree.

A binary tree is a binary search tree (BST) if all the non-empty nodes follows both two properties:

- If node has a left subtree, then all the values in its left subtree are smaller than the value of the current node.
- If node has a right subtree, then all the value in its right subtree are greater than the value of the current node.

You are givenÂ *N*Â nodes, each having unique value ranging fromÂ `[1, N]`

, how many different binary search tree can be created using all of them.

**Input**

First line will contain an integer,Â *T*, number of test cases. ThenÂ *T*Â lines follow, where each line represent a test case. Each test case consists a single integer,Â *N*, whereÂ *N*Â is the number of nodes in the binary search tree.

**Output**

For each test case, find the number of different binary search trees that can be created using these nodes. Print the answer modulo (10^{8}+7).

**Constraints**

- 1 <=Â
*T*Â <= 1000 - 1 <=Â
*N*Â <= 1000

**Sample Input**

```
5
1
2
3
4
100
```

**Sample Output**

```
1
2
5
14
25666077
```

**Explanation**

*Test Case #1:*Â We have only one tree.

`1`

*Test Case #2:*Â Two trees can be created using two nodes.

```
1 2
\ /
2 1
```

*Test Case #3:*

```
1 1 2 3 3
\ \ / \ / /
2 3 1 3 1 2
\ / \ /
3 2 2 1
```

**Solution – Number of Binary Search Tree – HackerRank Solution**

**Scala**

import java.util.Scanner import scala.collection.mutable object Solution { val modulo = 100000007 private val data = mutable.Map[Int, Long]() def solve(n: Int): Long = data.getOrElseUpdate(n, if (n <= 1) 1 else (0 until n).map(i => solve(i) * solve(n - i - 1) % modulo).sum % modulo) def main(args: Array[String]): Unit = { val sc = new Scanner(System.in) val t = sc.nextInt println((0 until t).map(_ => sc.nextInt).map(solve).mkString("\n")) } }

**Note:** This problem **(Number of Binary Search Tree)** is generated by **HackerRank** but the solution is provided by **CodingBroz**. This tutorial is only for **Educational** and **Learning** purpose.