Binary Tree in Java with Program Example

Problem Description

Write a Java Program to implement Binary Tree.

What is Binary Tree?
A binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as “left” and “right”. Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to the “root” node (the ancestor of all nodes), if it exists. Any node in the data structure can be reached by starting at the root node and repeatedly following references to either the left or right child. A tree that does not have any node other than root node is called a null tree. In a binary tree, a degree of every node is maximum two. A tree with n nodes has exactly n−1 branches or degree.

Binary trees are used to implement binary search trees and binary heaps, finding applications in efficient searching and sorting algorithms.

Binary Tree Operations:

Here are some common binary tree operations that can be implemented in Java:

1. Create a binary tree:
To create a binary tree, define a class for the nodes of the tree that contains two references (left and right) to the child nodes and a value to store the node’s data. Then, define a class for the binary tree that contains a reference to the root node of the tree.

2. Insert a node:
To insert a node into a binary tree, start at the root node and compare the new node’s value to the current node’s value. If the new node’s value is less than the current node’s value, go left; if it’s greater, go right. Repeat this process until an empty spot is found, then insert the new node.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

3. Delete a node:
To delete a node from a binary tree, first find the node to be deleted. Then, check the number of child nodes it has. If it has no child nodes, simply remove it. If it has one child node, replace it with its child. If it has two child nodes, replace it with the minimum value in its right subtree (or the maximum value in its left subtree) and then delete that node.

4. Search for a node:
To search for a node in a binary tree, start at the root node and compare the search value to the current node’s value. If the search value is less than the current node’s value, go left; if it’s greater, go right. Repeat this process until the node is found or an empty spot is reached.

5. Traverse the tree:
There are three common ways to traverse a binary tree: inorder, preorder, and postorder.

Check this: Programming MCQs | Computer Science Books

In inorder traversal, visit the left subtree, then the current node, then the right subtree.
In preorder traversal, visit the current node, then the left subtree, then the right subtree.
In postorder traversal, visit the left subtree, then the right subtree, then the current node.

6. Count the number of nodes:
To count the number of nodes in a binary tree, recursively count the number of nodes in each subtree and add them together. The number of nodes in the tree is the sum of the number of nodes in the left subtree, the number of nodes in the right subtree, and 1 (for the current node).

7. Check if the tree is empty:
To check if a binary tree is empty, simply check if the root node is null. If it is, the tree is empty.”

Program/Source Code

Here is the source code of the Java program to implement Binary Tree. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

```
/*
```

 *  Java Program to Implement Binary Tree

```
 */
```
```
 
```
```
 import java.util.Scanner;
```
```
 
```
```
 /* Class BTNode */
```
```
 class BTNode
```
```
 {    
```
```
     BTNode left, right;
```
```
     int data;
```
```
 
```
```
     /* Constructor */
```
```
     public BTNode()
```
```
     {
```
```
         left = null;
```
```
         right = null;
```
```
         data = 0;
```
```
     }
```
```
     /* Constructor */
```
```
     public BTNode(int n)
```
```
     {
```
```
         left = null;
```
```
         right = null;
```
```
         data = n;
```
```
     }
```
```
     /* Function to set left node */
```
```
     public void setLeft(BTNode n)
```
```
     {
```
```
         left = n;
```
```
     }
```
```
     /* Function to set right node */ 
```
```
     public void setRight(BTNode n)
```
```
     {
```
```
         right = n;
```
```
     }
```
```
     /* Function to get left node */
```
```
     public BTNode getLeft()
```
```
     {
```
```
         return left;
```
```
     }
```
```
     /* Function to get right node */
```
```
     public BTNode getRight()
```
```
     {
```
```
         return right;
```
```
     }
```
```
     /* Function to set data to node */
```
```
     public void setData(int d)
```
```
     {
```
```
         data = d;
```
```
     }
```

     /* Function to get data from node */

```
     public int getData()
```
```
     {
```
```
         return data;
```
```
     }     
```
```
 }
```
```
 
```
```
 /* Class BT */
```
```
 class BT
```
```
 {
```
```
     private BTNode root;
```
```
 
```
```
     /* Constructor */
```
```
     public BT()
```
```
     {
```
```
         root = null;
```
```
     }
```

     /* Function to check if tree is empty */

```
     public boolean isEmpty()
```
```
     {
```
```
         return root == null;
```
```
     }
```
```
     /* Functions to insert data */
```
```
     public void insert(int data)
```
```
     {
```
```
         root = insert(root, data);
```
```
     }
```

     /* Function to insert data recursively */

     private BTNode insert(BTNode node, int data)

```
     {
```
```
         if (node == null)
```
```
             node = new BTNode(data);
```
```
         else
```
```
         {
```

             if (node.getRight() == null)

                 node.right = insert(node.right, data);

```
             else
```

                 node.left = insert(node.left, data);

```
         }
```
```
         return node;
```
```
     }     
```

     /* Function to count number of nodes */

```
     public int countNodes()
```
```
     {
```
```
         return countNodes(root);
```
```
     }
```

     /* Function to count number of nodes recursively */

```
     private int countNodes(BTNode r)
```
```
     {
```
```
         if (r == null)
```
```
             return 0;
```
```
         else
```
```
         {
```
```
             int l = 1;
```

             l += countNodes(r.getLeft());

             l += countNodes(r.getRight());

```
             return l;
```
```
         }
```
```
     }
```

     /* Function to search for an element */

```
     public boolean search(int val)
```
```
     {
```
```
         return search(root, val);
```
```
     }
```

     /* Function to search for an element recursively */

     private boolean search(BTNode r, int val)

```
     {
```
```
         if (r.getData() == val)
```
```
             return true;
```
```
         if (r.getLeft() != null)
```

             if (search(r.getLeft(), val))

```
                 return true;
```
```
         if (r.getRight() != null)
```

             if (search(r.getRight(), val))

```
                 return true;
```
```
         return false;         
```
```
     }
```

     /* Function for inorder traversal */

```
     public void inorder()
```
```
     {
```
```
         inorder(root);
```
```
     }
```
```
     private void inorder(BTNode r)
```
```
     {
```
```
         if (r != null)
```
```
         {
```
```
             inorder(r.getLeft());
```

             System.out.print(r.getData() +" ");

```
             inorder(r.getRight());
```
```
         }
```
```
     }
```

     /* Function for preorder traversal */

```
     public void preorder()
```
```
     {
```
```
         preorder(root);
```
```
     }
```
```
     private void preorder(BTNode r)
```
```
     {
```
```
         if (r != null)
```
```
         {
```

             System.out.print(r.getData() +" ");

             preorder(r.getLeft());

```
             preorder(r.getRight());
```
```
         }
```
```
     }
```

     /* Function for postorder traversal */

```
     public void postorder()
```
```
     {
```
```
         postorder(root);
```
```
     }
```
```
     private void postorder(BTNode r)
```
```
     {
```
```
         if (r != null)
```
```
         {
```

             postorder(r.getLeft());

```
             postorder(r.getRight());
```

             System.out.print(r.getData() +" ");

```
         }
```
```
     }     
```
```
 }
```
```
 
```
```
 /* Class BinaryTree */
```
```
 public class BinaryTree
```
```
 {
```

     public static void main(String[] args)

```
    {            
```

        Scanner scan = new Scanner(System.in);

```
        /* Creating object of BT */
```
```
        BT bt = new BT(); 
```
```
        /*  Perform tree operations  */
```

        System.out.println("Binary Tree Test\n");

```
        char ch;        
```
```
        do    
```
```
        {
```

            System.out.println("\nBinary Tree Operations\n");

            System.out.println("1. insert ");

            System.out.println("2. search");

            System.out.println("3. count nodes");

            System.out.println("4. check empty");

```
 
```

            int choice = scan.nextInt();

```
            switch (choice)
```
```
            {
```
```
            case 1 : 
```

                System.out.println("Enter integer element to insert");

                bt.insert( scan.nextInt() );

                break;

```
            case 2 : 
```

                System.out.println("Enter integer element to search");

                System.out.println("Search result : "+ bt.search( scan.nextInt() ));

                break;

```
            case 3 : 
```

                System.out.println("Nodes = "+ bt.countNodes());

```
                break;     
```
```
            case 4 : 
```

                System.out.println("Empty status = "+ bt.isEmpty());

```
                break;            
```
```
            default : 
```

                System.out.println("Wrong Entry \n ");

```
                break;   
```
```
            }
```
```
            /*  Display tree  */ 
```

            System.out.print("\nPost order : ");

```
            bt.postorder();
```

            System.out.print("\nPre order : ");

```
            bt.preorder();
```

            System.out.print("\nIn order : ");

```
            bt.inorder();
```
```
 
```

            System.out.println("\n\nDo you want to continue (Type y or n) \n");

            ch = scan.next().charAt(0);

        } while (ch == 'Y'|| ch == 'y');

```
    }
```
```
 }
```

Program Explanation

1. It defines a class BTNode to represent a node of the binary tree, which contains left and right references to the left and right child nodes of the current node, and data to store the value of the node.
2. It has two constructors to initialize the node, one with a parameter to set the value of the node and the other without a parameter to set default values.
3. It defines a class BT to represent the binary tree, which contains

root reference to the root node of the tree.
A constructor to initialize the tree with a null root.
isEmpty function to check if the tree is empty.
insert function to insert a new node into the tree.
countNodes function to count the number of nodes in the tree.
search function to search for a value in the tree.
Three traversal functions (inorder, preorder, postorder) to traverse the tree in different orders.

4. It defines a class BinaryTree with the main method to create an instance of BT and perform tree operations.
5. It creates a new instance of BT, displays a menu of tree operations to the user, reads the user’s choice, performs the selected operation on the tree, displays the tree after each operation by traversing the tree in pre-order, in-order, and post-order, and asks the user if they want to continue with the operations or not.
6. In the main method, it creates a new instance of Scanner to read user input and starts a do-while loop to continue tree operations until the user chooses to exit.

Runtime Test Cases

Here is the implementation of Binary tree.

Binary Tree Test
 
 
Binary Tree Operations
 
1. insert
2. search
3. count nodes
4. check empty
4
Empty status = true
 
Post order :
Pre order :
In order :
 
Do you want to continue (Type y or n)
 
y
 
Binary Tree Operations
 
1. insert
2. search
3. count nodes
4. check empty
1
Enter integer element to insert
6
 
Post order : 6
Pre order : 6
In order : 6
 
Do you want to continue (Type y or n)
 
y
 
Binary Tree Operations
 
1. insert
2. search
3. count nodes
4. check empty
1
Enter integer element to insert
24
 
Post order : 24 6
Pre order : 6 24
In order : 6 24
 
Do you want to continue (Type y or n)
 
y
 
Binary Tree Operations
 
1. insert
2. search
3. count nodes
4. check empty
1
Enter integer element to insert
19
 
Post order : 19 24 6
Pre order : 6 19 24
In order : 19 6 24
 
Do you want to continue (Type y or n)
 
y
 
Binary Tree Operations
 
1. insert
2. search
3. count nodes
4. check empty
1
Enter integer element to insert
94
 
Post order : 94 19 24 6
Pre order : 6 19 94 24
In order : 19 94 6 24
 
Do you want to continue (Type y or n)
 
y
 
Binary Tree Operations
 
1. insert
2. search
3. count nodes
4. check empty
1
Enter integer element to insert
5
 
Post order : 5 94 19 24 6
Pre order : 6 19 5 94 24
In order : 5 19 94 6 24
 
Do you want to continue (Type y or n)
 
y
 
Binary Tree Operations
 
1. insert
2. search
3. count nodes
4. check empty
1
Enter integer element to insert
1
 
Post order : 1 5 94 19 24 6
Pre order : 6 19 5 1 94 24
In order : 5 1 19 94 6 24
 
Do you want to continue (Type y or n)
 
y
 
Binary Tree Operations
 
1. insert
2. search
3. count nodes
4. check empty
1
Enter integer element to insert
10
 
Post order : 10 1 5 94 19 24 6
Pre order : 6 19 5 10 1 94 24
In order : 10 5 1 19 94 6 24
 
Do you want to continue (Type y or n)
 
y
 
Binary Tree Operations
 
1. insert
2. search
3. count nodes
4. check empty
1
Enter integer element to insert
3
 
Post order : 3 10 1 5 94 19 24 6
Pre order : 6 19 5 10 3 1 94 24
In order : 10 3 5 1 19 94 6 24
 
Do you want to continue (Type y or n)
 
y
 
Binary Tree Operations
 
1. insert
2. search
3. count nodes
4. check empty
1
Enter integer element to insert
8
 
Post order : 8 3 10 1 5 94 19 24 6
Pre order : 6 19 5 10 8 3 1 94 24
In order : 8 10 3 5 1 19 94 6 24
 
Do you want to continue (Type y or n)
 
y
 
Binary Tree Operations
 
1. insert
2. search
3. count nodes
4. check empty
3
Nodes = 9
 
Post order : 8 3 10 1 5 94 19 24 6
Pre order : 6 19 5 10 8 3 1 94 24
In order : 8 10 3 5 1 19 94 6 24
 
Do you want to continue (Type y or n)
 
y
 
Binary Tree Operations
 
1. insert
2. search
3. count nodes
4. check empty
2
Enter integer element to search
24
Search result : true
 
Post order : 8 3 10 1 5 94 19 24 6
Pre order : 6 19 5 10 8 3 1 94 24
In order : 8 10 3 5 1 19 94 6 24
 
Do you want to continue (Type y or n)
 
y
 
Binary Tree Operations
 
1. insert
2. search
3. count nodes
4. check empty
2
Enter integer element to search
7
Search result : false
 
Post order : 8 3 10 1 5 94 19 24 6
Pre order : 6 19 5 10 8 3 1 94 24
In order : 8 10 3 5 1 19 94 6 24
 
Do you want to continue (Type y or n)
 
n

To practice programs on every topic in Java, please visit “Programming Examples in Java”, “Data Structures in Java” and “Algorithms in Java”.

« Prev - Java Program to Implement AVL Tree

» Next - Java Program to Implement AA Tree

Next Steps: