Java program to find the total number of possible Binary Search Trees with N keys

by Online Tutorials Library July 22, 2022

Java program to find the total number of possible Binary Search Trees with N keys

In this program, we need to find out the total number of binary search trees can be constructed with n values. Below diagram shows a possible binary search tree with the key value as 3. So, we can construct a total of five binary search trees. When we choose node 1 as the root node, we get two trees. Similarly, one tree with 2 as root nodes and two trees when we select 3 as the root node.

This approach involves selecting a node recursively as the root node and create possible binary search tree.

An easy way to calculate the total number of possible binary search trees are through Catalan number:

Java program to find the total number of possible Binary Search Trees with N keys

Algorithm

Define Node class which has three attributes namely: data left and right. Here, left represents the left child of the node and right represents the right child of the node.
When a node is created, data will be passed to the data attribute of the node and both left and right will be set to null.
Define another class which has an attribute root.
- Root represents the root node of the tree and initializes it to null.

a. numOfBST() will find out total possible binary search tree for given key:

It will calculate the Catalan number for given key by making a call to factorial().
Catalan number can be calculated using the formula:
Cn = (2n)! / n! *(n+1)!
Factorial() will calculate factorial of a given number.

Program:

  public class BinarySearchTree {        //Represent the node of binary tree      public static class Node{          int data;          Node left;          Node right;            public Node(int data){              //Assign data to the new node, set left and right children to null              this.data = data;              this.left = null;              this.right = null;              }          }        //Represent the root of binary tree      public Node root;        public BinarySearchTree(){          root = null;      }        //factorial() will calculate the factorial of given number      public int factorial(int num) {          int fact = 1;          if(num == 0)              return 1;          else {              while(num > 1) {                  fact = fact * num;                  num–;              }              return fact;          }      }        //numOfBST() will calculate the total number of possible BST by calculating Catalan Number for given key      public int numOfBST(int key) {          int catalanNumber = factorial(2 * key)/(factorial(key + 1) * factorial(key));          return catalanNumber;      }        public static void main(String[] args) {            BinarySearchTree bt = new BinarySearchTree();            //Display total number of possible binary search tree with key 5          System.out.println(“Total number of possible Binary Search Trees with given key: ” + bt.numOfBST(5));        }  }  

Output:

Total number of possible Binary Search Trees with given key: 42

Next TopicJava Programs

Java program to find the total number of possible Binary Search Trees with N keys

Java program to find the total number of possible Binary Search Trees with N keys

Algorithm

Program:

Java Logo

Java Program to print the duplicate elements of an array

You may also like