Java program to implement Binary Tree using the Linked List

In the following example of Java program to implement a binary tree using a linked list :

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

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 pass to 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 initialize it to null.

* a. insert() will add a new node to the tree:

* It checks whether the root is null, which means the tree is empty. It will add the new node as root.

* Else, it will add root to the queue.

* The variable node represents the current node.

* First, it checks whether a node has a left and right child. If yes, it will add both nodes to queue.

* If the left child is not present, it will add the new node as the left child.

* If the left is present, then it will add the new node as the right child.

* a. Inorder() will display nodes of the tree in inorder fashion.

* It traverses the entire tree then prints out left child followed by root then followed by the right child.