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.

Task

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 (10⁸+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.