Java Program to Perform Insertion in Binary Search Tree

«
»
This is a Java Program to perform insertion in the binary search tree.

Here is the source code of the Java Program to Perform Insertion in a BST. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. //This is a java program to insert elements in a Binary Search Tree
  2. import java.util.Scanner;
  3.  
  4. class BSTNode
  5. {
  6.     BSTNode left, right;
  7.     int     data;
  8.  
  9.     public BSTNode()
  10.     {
  11.         left = null;
  12.         right = null;
  13.         data = 0;
  14.     }
  15.  
  16.     public BSTNode(int n)
  17.     {
  18.         left = null;
  19.         right = null;
  20.         data = n;
  21.     }
  22.  
  23.     public void setLeft(BSTNode n)
  24.     {
  25.         left = n;
  26.     }
  27.  
  28.     public void setRight(BSTNode n)
  29.     {
  30.         right = n;
  31.     }
  32.  
  33.     public BSTNode getLeft()
  34.     {
  35.         return left;
  36.     }
  37.  
  38.     public BSTNode getRight()
  39.     {
  40.         return right;
  41.     }
  42.  
  43.     public void setData(int d)
  44.     {
  45.         data = d;
  46.     }
  47.  
  48.     public int getData()
  49.     {
  50.         return data;
  51.     }
  52. }
  53.  
  54. class BSTree
  55. {
  56.     private BSTNode root;
  57.  
  58.     public BSTree()
  59.     {
  60.         root = null;
  61.     }
  62.  
  63.     public boolean isEmpty()
  64.     {
  65.         return root == null;
  66.     }
  67.  
  68.     public void insert(int data)
  69.     {
  70.         root = insert(root, data);
  71.     }
  72.  
  73.     private BSTNode insert(BSTNode node, int data)
  74.     {
  75.         if (node == null)
  76.             node = new BSTNode(data);
  77.         else
  78.         {
  79.             if (data <= node.getData())
  80.                 node.left = insert(node.left, data);
  81.             else
  82.                 node.right = insert(node.right, data);
  83.         }
  84.         return node;
  85.     }
  86.  
  87.     public void inorder()
  88.     {
  89.         inorder(root);
  90.     }
  91.  
  92.     private void inorder(BSTNode r)
  93.     {
  94.         if (r != null)
  95.         {
  96.             inorder(r.getLeft());
  97.             System.out.print(r.getData() + " ");
  98.             inorder(r.getRight());
  99.         }
  100.     }
  101.  
  102.     public void preorder()
  103.     {
  104.         preorder(root);
  105.     }
  106.  
  107.     private void preorder(BSTNode r)
  108.     {
  109.         if (r != null)
  110.         {
  111.             System.out.print(r.getData() + " ");
  112.             preorder(r.getLeft());
  113.             preorder(r.getRight());
  114.         }
  115.     }
  116.  
  117.     public void postorder()
  118.     {
  119.         postorder(root);
  120.     }
  121.  
  122.     private void postorder(BSTNode r)
  123.     {
  124.         if (r != null)
  125.         {
  126.             postorder(r.getLeft());
  127.             postorder(r.getRight());
  128.             System.out.print(r.getData() + " ");
  129.         }
  130.     }
  131. }
  132.  
  133. public class Insertion_BST
  134. {
  135.     public static void main(String[] args)
  136.     {
  137.         Scanner scan = new Scanner(System.in);
  138.         BSTree bst = new BSTree();
  139.         System.out.println("Binary Search Tree Insertion Test\n");
  140.         int N = 10;
  141.         for (int i = 0; i < N; i++)
  142.         {
  143.             bst.insert(scan.nextInt());
  144.             System.out.print("\nPost order : ");
  145.             bst.postorder();
  146.             System.out.print("\nPre order  : ");
  147.             bst.preorder();
  148.             System.out.print("\nIn order   : ");
  149.             bst.inorder();
  150.         }
  151.         scan.close();
  152.     }
  153. }

Output:

advertisement
$ java Insertion_BST.java
$ java Insertion_BST
 
Binary Search Tree Insertion Test
 
Add element: 3
 
Post order : 3 
Pre order  : 3 
In order   : 3 
 
Add element: 5
 
Post order : 5 3 
Pre order  : 3 5 
In order   : 3 5 
 
Add element: 4
 
Post order : 4 5 3 
Pre order  : 3 5 4 
In order   : 3 4 5 
 
Add element: 4
 
Post order : 4 4 5 3 
Pre order  : 3 5 4 4 
In order   : 3 4 4 5 
 
Add element: 6
 
Post order : 4 4 6 5 3 
Pre order  : 3 5 4 4 6 
In order   : 3 4 4 5 6 
 
Add element: 45
 
Post order : 4 4 45 6 5 3 
Pre order  : 3 5 4 4 6 45 
In order   : 3 4 4 5 6 45 
 
Add element: 7578
 
Post order : 4 4 7578 45 6 5 3 
Pre order  : 3 5 4 4 6 45 7578 
In order   : 3 4 4 5 6 45 7578 
 
Add element: 54651
 
Post order : 4 4 54651 7578 45 6 5 3 
Pre order  : 3 5 4 4 6 45 7578 54651 
In order   : 3 4 4 5 6 45 7578 54651 
 
Add element: 22
 
Post order : 4 4 22 54651 7578 45 6 5 3 
Pre order  : 3 5 4 4 6 45 22 7578 54651 
In order   : 3 4 4 5 6 22 45 7578 54651 
 
Add element: 34
 
Post order : 4 4 34 22 54651 7578 45 6 5 3 
Pre order  : 3 5 4 4 6 45 22 34 7578 54651 
In order   : 3 4 4 5 6 22 34 45 7578 54651

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

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.