Binary Tree Post Order Traversal inwards Java Without Recursion - Example Tutorial

In the in conclusion article, I convey shown y'all how to implement post service lodge traversal inwards a binary tree using recursion too today I am going to instruct y'all virtually post service lodge traversal without recursion. To live honest, the iterative algorithm of post-order traversal is the toughest with the iterative pre-order too in-order traversal algorithm. The procedure of post service lodge traversal remains same but the algorithm to accomplish that lawsuit is different. Since post-order traversal is a depth-first algorithm, y'all become deep earlier y'all become wide. The left subtree is visited first, followed yesteryear correct subtree too finally the value of a node is printed. This is the argue why the value of origin is printed in conclusion inwards the post-order traversal algorithm.

Now, let's meet the utility of post-order traversal algorithm, what exercise y'all acquire from it too when exercise y'all purpose the post-order algorithm to traverse a binary tree? As oppose to inorder traversal which prints node of the binary search tree inwards sorted lodge too tin also live used to flatten a binary tree inwards the same lodge it was created, post-order traversal tin live used to inspect leaves earlier y'all inspect root. It tin also live used to generate postfix sequence.

Now, 1 of the oft asked questions is when exercise y'all purpose pre-order, post-order, or in-order traversal piece dealing with binary tree information structure? The full general betoken regarding usage of traversal algorithm is based on the requirement of your application e.g. if y'all desire to inspect all roots earlier leaves purpose pre-order too if y'all desire to inspect leaves earlier origin hence purpose post-order traversal.

If y'all desire to see all nodes inwards the sorted lodge hence y'all tin purpose in-order traversal algorithm. You tin also read Introduction to Algorithms to larn to a greater extent than virtually when to purpose pre-order, in-order, too post-order traversals.

Iterative Algorithm to implement post service lodge traversal of Binary Tree

The recursive algorithm of post service lodge traversal which nosotros convey seen inwards the previous article was quite similar to recursive pre-order too recursive inwards order algorithms, all y'all demand y'all to exercise was adapt the lodge of recursive business office telephone call upward to gibe the lodge on which left subtree, correct subtree, too origin needs to traversed, but iterative algorithm of post-order traversal is really dissimilar than iterative pre-order too in-order traversal.

In fact, it's the most hard to implement with iii traversal algorithm. Sure, y'all withal purpose an explicitly Stack information construction to shop elements, but the backtracking too hence exploring correct subtree is a piddling flake tricky to implement.

Here is 1 of the simplest post-order traversal algorithm without using recursion:

public void postOrderWithoutRecursion() {     Stack<TreeNode> nodes = new Stack<>();     nodes.push(root);      while (!nodes.isEmpty()) {       TreeNode electrical flow = nodes.peek();        if (current.isLeaf()) {         TreeNode node = nodes.pop();         System.out.printf("%s ", node.data);       } else {          if (current.right != null) {           nodes.push(current.right);           current.right = null;         }          if (current.left != null) {           nodes.push(current.left);           current.left = null;         }       }      }   }

If y'all expect at this method y'all volition detect that nosotros are examining leaves earlier examining root. We start the post service lodge traversal from the origin yesteryear pushing it into a Stack too hence loop until out Stack is empty. At each iteration, nosotros peek() the chemical ingredient from Stack i.e. retrieve it without removing too depository fiscal establishment check if it's a leaf, if yep hence nosotros pop() the chemical ingredient too impress its value, which agency the node is visited.

If it's non a foliage hence nosotros depository fiscal establishment check if it has a correct node, if yep nosotros shop into a tree too laid it to null, similarly, nosotros depository fiscal establishment check if it has left a node, if yep nosotros force into the stack too hence grade it null. We starting fourth dimension insert correct node because Stack is a LIFO (last inwards starting fourth dimension out) information construction too equally per post service lodge traversal nosotros demand to explore left subtree earlier correct subtree

Java Program for Binary tree PostOrder traversal

Here is our consummate Java plan to implement post service lodge traversal of a binary tree inwards Java without using recursion. The iterative algorithm is encapsulated within the postOrder() method. We convey used the same BinaryTree too TreeNode floor to implement binary tree too hence added the postOrder() method to impress all nodes of a binary tree into post service order. The algorithm nosotros convey used doesn't demand recursion too it instead uses a piece loop too a Stack, traditional tool to convert a recursive algorithm to an iterative one.

import java.util.Stack;  /*  * Java Program to traverse a binary tree   * using postOrder traversal without recursion.   * In postOrder traversal starting fourth dimension left subtree is visited,     followed yesteryear correct subtree  * too finally information of origin or electrical flow node is printed.  *   * input:  * 55  * / \  * 35 65  * / \ \  * 25 45 75  * / / \  * xv 87 98  *   * output: xv 25 45 35 87 98 75 65 55   */  public class Main {    public static void main(String[] args) throws Exception {      // build the binary tree given inwards question     BinaryTree bt = BinaryTree.create();      // traversing binary tree on post service lodge traversal without recursion     System.out         .println("printing nodes of binary tree on post service lodge using iteration");     bt.postOrderWithoutRecursion();   }  }  class BinaryTree {   static class TreeNode {     String data;     TreeNode left, right;      TreeNode(String value) {       this.data = value;       left = correct = null;     }      boolean isLeaf() {       return left == zippo ? correct == zippo : false;     }    }    // origin of binary tree   TreeNode root;    /**    * Java method to impress all nodes of tree inwards post-order traversal    */   public void postOrderWithoutRecursion() {     Stack<TreeNode> nodes = new Stack<>();     nodes.push(root);      while (!nodes.isEmpty()) {       TreeNode electrical flow = nodes.peek();        if (current.isLeaf()) {         TreeNode node = nodes.pop();         System.out.printf("%s ", node.data);       } else {          if (current.right != null) {           nodes.push(current.right);           current.right = null;         }          if (current.left != null) {           nodes.push(current.left);           current.left = null;         }       }      }   }    /**    * Java method to exercise binary tree with examine information    *     * @return a sample binary tree for testing    */   public static BinaryTree create() {     BinaryTree tree = new BinaryTree();     TreeNode origin = new TreeNode("55");     tree.root = root;     tree.root.left = new TreeNode("35");     tree.root.left.left = new TreeNode("25");     tree.root.left.left.left = new TreeNode("15");      tree.root.left.right = new TreeNode("45");     tree.root.right = new TreeNode("65");     tree.root.right.right = new TreeNode("75");     tree.root.right.right.left = new TreeNode("87");     tree.root.right.right.right = new TreeNode("98");      return tree;   }  }

When y'all volition run this plan inwards your favorite IDE e.g. Eclipse or IntelliJIDea, y'all volition meet the next output:

Output printing nodes of a binary tree on post service lodge using iteration 15 25 45 35 87 98 75 65 55

You tin meet that nodes are printed inwards the post service order. You tin also meet the value of origin node is printed last.

how to implement post service lodge traversal inwards a binary tree using recursion Binary Tree Post Order Traversal inwards Java Without Recursion - Example Tutorial

That's all virtually how to implement post service lodge traversal of a binary tree inwards Java. Just remember, it is also a depth-first algorithm, but y'all demand to see the left subtree first, followed yesteryear correct subtree too root. The iterative version is also really hard to implement y'all become precisely yesteryear the steps of post-order traversal. The version which I convey shared is much easier to empathize too implement.

Further Learning
Algorithms too Data Structures - Part 1 too ii
Java Fundamentals, Part 1 too 2
Cracking the Coding Interview - 189 Questions too Solutions

Other Data Structure too Algorithm tutorials in Java, you may similar to explore

Top five information construction too algorithm books for coding interviews (list)
Java Program to traverse binary tree inwards pre-order without recursion (program)
How to impress all foliage nodes of a binary tree inwards Java? (solution)
Java Program to impress foliage nodes of a binary tree without recursion? (program)
How to traverse a binary tree inwards pre-order without using recursion? (solution)
How to impress all foliage nodes of a binary tree without recursion inwards Java? (solution)
How to implement linked listing using generic inwards Java? (solution)
How to contrary a singly linked listing inwards Java? (solution)
How to detect the third chemical ingredient from the goal of linked listing inwards Java? (solution)
How to detect the middle chemical ingredient of linked listing using unmarried pass? (solution)
Java plan to implement binary search using recursion? (solution)
How to contrary an array inwards house inwards Java? (solution)
How to impress duplicate elements of an array inwards Java? (solution)

Thanks for reading this article hence far. If y'all similar this tutorial too interview inquiry hence delight portion with your friends too colleagues. If y'all convey whatever feedback or inquiry hence delight drib a comment too I'll endeavour to respond your query. If y'all desire to larn to a greater extent than virtually essential information structures too algorithms hence merely read Introduction to Algorithms.