# Number of Binary Search Tree – HackerRank Solution

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.

Contents

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

1. It can be empty (null).
2. 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:

1. If node has a left subtree, then all the values in its left subtree are smaller than the value of the current node.
2. 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 (108+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.