Inorder Traversal of a Binary Tree without using Recursion in Java

This is a java program to construct a binary tree and perform in-order traversal of the constructed binary tree.
Nodes visited are in the order:
visit Left node
visit Root node
visit Right node

Here is the source code of the Java Program to Perform Inorder Non-Recursive Traversal of a Given Binary Tree. 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 implement non recursive in order traversal of Binary Search Tree
  2. import java.util.Scanner;
  3. import java.util.Stack;
  4.  
  5. class BinarySearchTreeNode
  6. {
  7.     BinarySearchTreeNode left, right;
  8.     int                  data;
  9.  
  10.     public BinarySearchTreeNode()
  11.     {
  12.         left = null;
  13.         right = null;
  14.         data = 0;
  15.     }
  16.  
  17.     public BinarySearchTreeNode(int n)
  18.     {
  19.         left = null;
  20.         right = null;
  21.         data = n;
  22.     }
  23.  
  24.     public void setLeft(BinarySearchTreeNode n)
  25.     {
  26.         left = n;
  27.     }
  28.  
  29.     public void setRight(BinarySearchTreeNode n)
  30.     {
  31.         right = n;
  32.     }
  33.  
  34.     public BinarySearchTreeNode getLeft()
  35.     {
  36.         return left;
  37.     }
  38.  
  39.     public BinarySearchTreeNode getRight()
  40.     {
  41.         return right;
  42.     }
  43.  
  44.     public void setData(int d)
  45.     {
  46.         data = d;
  47.     }
  48.  
  49.     public int getData()
  50.     {
  51.         return data;
  52.     }
  53. }
  54.  
  55. class BinarySearchTreeOperations
  56. {
  57.     private BinarySearchTreeNodes root;
  58.  
  59.     public BinarySearchTreeOperations()
  60.     {
  61.         root = null;
  62.     }
  63.  
  64.     public boolean isEmpty()
  65.     {
  66.         return root == null;
  67.     }
  68.  
  69.     public void insert(int data)
  70.     {
  71.         root = insert(root, data);
  72.     }
  73.  
  74.     private BinarySearchTreeNodes insert(BinarySearchTreeNodes node, int data)
  75.     {
  76.         if (node == null)
  77.             node = new BinarySearchTreeNodes(data);
  78.         else
  79.         {
  80.             if (data <= node.getData())
  81.                 node.left = insert(node.left, data);
  82.             else
  83.                 node.right = insert(node.right, data);
  84.         }
  85.         return node;
  86.     }
  87.  
  88.     public void inorder()
  89.     {
  90.         inorder(root);
  91.     }
  92.  
  93.     private void inorder(BinarySearchTreeNodes r)
  94.     {
  95.         if (r == null)
  96.             return;
  97.  
  98.         Stack<BinarySearchTreeNodes> stack = new Stack<BinarySearchTreeNodes>();
  99.  
  100.         while (!stack.isEmpty() || r != null)
  101.         {
  102.             if (r != null)
  103.             {
  104.                 stack.push(r);
  105.                 r = r.left;
  106.             } else
  107.             {
  108.                 r = stack.pop();
  109.                 System.out.print(r.data + " ");
  110.                 r = r.right;
  111.             }
  112.         }
  113.     }
  114. }
  115.  
  116. public class Inorder_NonRecursive_BST
  117. {
  118.     public static void main(String[] args)
  119.     {
  120.         Scanner scan = new Scanner(System.in);
  121.         BinarySearchTreeOperations bst = new BinarySearchTreeOperations();
  122.         System.out.println("Enter the first 10 elements of the tree\n");
  123.         int N = 10;
  124.         for (int i = 0; i < N; i++)
  125.             bst.insert(scan.nextInt());
  126.  
  127.         System.out.print("\nIn order   : ");
  128.         bst.inorder();
  129.  
  130.         scan.close();
  131.     }
  132. }

Output:

$ javac Inorder_NonRecursive_BST.java
$ java Inorder_NonRecursive_BST
 
Enter the first 10 elements of the tree
 
12 4 10 13 15 46 78 98 45 12
 
In order   : 4 10 12 12 13 15 45 46 78 98

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 & discussions at Telegram SanfoundryClasses.