Java Program to Implement Binary Tree

«
»
This is a Java Program to implement 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 root node and repeatedly following references to either the left or right child. A tree which 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.

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.

  1. /*
  2.  *  Java Program to Implement Binary Tree
  3.  */
  4.  
  5.  import java.util.Scanner;
  6.  
  7.  /* Class BTNode */
  8.  class BTNode
  9.  {    
  10.      BTNode left, right;
  11.      int data;
  12.  
  13.      /* Constructor */
  14.      public BTNode()
  15.      {
  16.          left = null;
  17.          right = null;
  18.          data = 0;
  19.      }
  20.      /* Constructor */
  21.      public BTNode(int n)
  22.      {
  23.          left = null;
  24.          right = null;
  25.          data = n;
  26.      }
  27.      /* Function to set left node */
  28.      public void setLeft(BTNode n)
  29.      {
  30.          left = n;
  31.      }
  32.      /* Function to set right node */ 
  33.      public void setRight(BTNode n)
  34.      {
  35.          right = n;
  36.      }
  37.      /* Function to get left node */
  38.      public BTNode getLeft()
  39.      {
  40.          return left;
  41.      }
  42.      /* Function to get right node */
  43.      public BTNode getRight()
  44.      {
  45.          return right;
  46.      }
  47.      /* Function to set data to node */
  48.      public void setData(int d)
  49.      {
  50.          data = d;
  51.      }
  52.      /* Function to get data from node */
  53.      public int getData()
  54.      {
  55.          return data;
  56.      }     
  57.  }
  58.  
  59.  /* Class BT */
  60.  class BT
  61.  {
  62.      private BTNode root;
  63.  
  64.      /* Constructor */
  65.      public BT()
  66.      {
  67.          root = null;
  68.      }
  69.      /* Function to check if tree is empty */
  70.      public boolean isEmpty()
  71.      {
  72.          return root == null;
  73.      }
  74.      /* Functions to insert data */
  75.      public void insert(int data)
  76.      {
  77.          root = insert(root, data);
  78.      }
  79.      /* Function to insert data recursively */
  80.      private BTNode insert(BTNode node, int data)
  81.      {
  82.          if (node == null)
  83.              node = new BTNode(data);
  84.          else
  85.          {
  86.              if (node.getRight() == null)
  87.                  node.right = insert(node.right, data);
  88.              else
  89.                  node.left = insert(node.left, data);             
  90.          }
  91.          return node;
  92.      }     
  93.      /* Function to count number of nodes */
  94.      public int countNodes()
  95.      {
  96.          return countNodes(root);
  97.      }
  98.      /* Function to count number of nodes recursively */
  99.      private int countNodes(BTNode r)
  100.      {
  101.          if (r == null)
  102.              return 0;
  103.          else
  104.          {
  105.              int l = 1;
  106.              l += countNodes(r.getLeft());
  107.              l += countNodes(r.getRight());
  108.              return l;
  109.          }
  110.      }
  111.      /* Function to search for an element */
  112.      public boolean search(int val)
  113.      {
  114.          return search(root, val);
  115.      }
  116.      /* Function to search for an element recursively */
  117.      private boolean search(BTNode r, int val)
  118.      {
  119.          if (r.getData() == val)
  120.              return true;
  121.          if (r.getLeft() != null)
  122.              if (search(r.getLeft(), val))
  123.                  return true;
  124.          if (r.getRight() != null)
  125.              if (search(r.getRight(), val))
  126.                  return true;
  127.          return false;         
  128.      }
  129.      /* Function for inorder traversal */
  130.      public void inorder()
  131.      {
  132.          inorder(root);
  133.      }
  134.      private void inorder(BTNode r)
  135.      {
  136.          if (r != null)
  137.          {
  138.              inorder(r.getLeft());
  139.              System.out.print(r.getData() +" ");
  140.              inorder(r.getRight());
  141.          }
  142.      }
  143.      /* Function for preorder traversal */
  144.      public void preorder()
  145.      {
  146.          preorder(root);
  147.      }
  148.      private void preorder(BTNode r)
  149.      {
  150.          if (r != null)
  151.          {
  152.              System.out.print(r.getData() +" ");
  153.              preorder(r.getLeft());             
  154.              preorder(r.getRight());
  155.          }
  156.      }
  157.      /* Function for postorder traversal */
  158.      public void postorder()
  159.      {
  160.          postorder(root);
  161.      }
  162.      private void postorder(BTNode r)
  163.      {
  164.          if (r != null)
  165.          {
  166.              postorder(r.getLeft());             
  167.              postorder(r.getRight());
  168.              System.out.print(r.getData() +" ");
  169.          }
  170.      }     
  171.  }
  172.  
  173.  /* Class BinaryTree */
  174.  public class BinaryTree
  175.  {
  176.      public static void main(String[] args)
  177.     {            
  178.         Scanner scan = new Scanner(System.in);
  179.         /* Creating object of BT */
  180.         BT bt = new BT(); 
  181.         /*  Perform tree operations  */
  182.         System.out.println("Binary Tree Test\n");          
  183.         char ch;        
  184.         do    
  185.         {
  186.             System.out.println("\nBinary Tree Operations\n");
  187.             System.out.println("1. insert ");
  188.             System.out.println("2. search");
  189.             System.out.println("3. count nodes");
  190.             System.out.println("4. check empty");
  191.  
  192.             int choice = scan.nextInt();            
  193.             switch (choice)
  194.             {
  195.             case 1 : 
  196.                 System.out.println("Enter integer element to insert");
  197.                 bt.insert( scan.nextInt() );                     
  198.                 break;                          
  199.             case 2 : 
  200.                 System.out.println("Enter integer element to search");
  201.                 System.out.println("Search result : "+ bt.search( scan.nextInt() ));
  202.                 break;                                          
  203.             case 3 : 
  204.                 System.out.println("Nodes = "+ bt.countNodes());
  205.                 break;     
  206.             case 4 : 
  207.                 System.out.println("Empty status = "+ bt.isEmpty());
  208.                 break;            
  209.             default : 
  210.                 System.out.println("Wrong Entry \n ");
  211.                 break;   
  212.             }
  213.             /*  Display tree  */ 
  214.             System.out.print("\nPost order : ");
  215.             bt.postorder();
  216.             System.out.print("\nPre order : ");
  217.             bt.preorder();
  218.             System.out.print("\nIn order : ");
  219.             bt.inorder();
  220.  
  221.             System.out.println("\n\nDo you want to continue (Type y or n) \n");
  222.             ch = scan.next().charAt(0);                        
  223.         } while (ch == 'Y'|| ch == 'y');               
  224.     }
  225.  }

advertisement
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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.