Postorder Traversal of a Binary Tree without using Recursion in Java

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

Here is the source code of the Java Program to Perform Postorder 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 post 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 postorder()
  89.     {
  90.         postorder(root);
  91.     }
  92.  
  93.     private void postorder(BinarySearchTreeNodes r)
  94.     {
  95.         if (root == null)
  96.             return;
  97.  
  98.         final Stack<BinarySearchTreeNodes> stack = new Stack<BinarySearchTreeNodes>();
  99.         BinarySearchTreeNodes node = root;
  100.  
  101.         while (!stack.isEmpty() || node != null)
  102.         {
  103.             while (node != null)
  104.             {
  105.                 if (node.right != null)
  106.                     stack.add(node.right);
  107.                 stack.add(node);
  108.                 node = node.left;
  109.             }
  110.  
  111.             node = stack.pop();
  112.  
  113.             if (node.right != null && !stack.isEmpty()
  114.                     && node.right == stack.peek())
  115.             {
  116.                 BinarySearchTreeNodes nodeRight = stack.pop();
  117.                 stack.push(node);
  118.                 node = nodeRight;
  119.             } else
  120.             {
  121.                 System.out.print(node.data + " ");
  122.                 node = null;
  123.             }
  124.         }
  125.     }
  126. }
  127.  
  128. public class Postorder_NonRecursive_BST
  129. {
  130.     public static void main(String[] args)
  131.     {
  132.         Scanner scan = new Scanner(System.in);
  133.         BinarySearchTreeOperations bst = new BinarySearchTreeOperations();
  134.         System.out.println("Enter the first 10 elements of the tree\n");
  135.         int N = 10;
  136.         for (int i = 0; i < N; i++)
  137.             bst.insert(scan.nextInt());
  138.  
  139.         System.out.print("\nPost order : ");
  140.         bst.postorder();
  141.  
  142.         scan.close();
  143.     }
  144. }

Output:

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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
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.