Java program to implement Binary Tree using the Linked List

by Online Tutorials Library July 22, 2022

Java program to implement Binary Tree using the Linked List

In this program, we need to create the binary tree by inserting nodes and displaying nodes in in-order fashion. A typical binary tree can be represented as follows:

In the binary tree, each node can have at most two children. Each node can have zero, one or two children. Each node in the binary tree contains the following information:

Java program to implement Binary Tree using the Linked List

Data that represents value stored in the node.

Left that represents the pointer to the left child.

Right that represents the pointer to the right child.

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.

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:

Binary tree after insertion  1   Binary tree after insertion  2 1 3   Binary tree after insertion  4 2 5 1 3   Binary tree after insertion  4 2 5 1 6 3 7

Next TopicJava Programs

Java program to implement Binary Tree using the Linked List

Java program to implement Binary Tree using the Linked List

Algorithm

Program:

Java Logo

Java Program to print the duplicate elements of an array

You may also like