Post Guild Binary Tree Traversal Inward Coffee - Recursion Too Iteration Example

This is the 3rd article on tree traversal. In the in conclusion twain of articles, I receive got shown you lot how to implement preorder as well as inorder traversal inwards Java, both recursively as well as iteratively as well as today, you lot volition larn close the post social club traversal. Out of these iii principal tree traversal algorithms, the post-order traversal is most difficult to implement, especially the iterative version. In postal service social club traversal, you lot showtime see left subtree, as well as thence correct subtree as well as at in conclusion you lot impress the value of root or not. So, the value of root is ever printed at in conclusion inwards the post-order traversal. As I told you lot before, all iii preOrder, inOrder, as well as postOrder are depth-first algorithms thence they become downward inwards the binary tree showtime earlier visiting nodes of the same level. The implementation of the recursive algorithm is really simple, you lot simply require to adapt the social club of recursive telephone squall upwards according to the algorithm as well as you lot are done, but iterative algorithm requires approximately endeavour to acquire it right, which you lot volition meet inwards this article.


Unlike inorder traversal which prints the nodes of binary search tree inwards sorted order, postal service social club doesn't impress values inwards sorted social club but it tin hold upwards used to generate a postfix representation of a binary tree. It's too especially of import spell deleting nodes of binary tree e.g. if you lot don't move post-order traversal during deletion, as well as thence you lot lose the references you lot require for deleting the nipper trees. These were simply twain of usage of postal service social club tree traversal, you lot tin meet a proficient algorithm majority similar Introduction to Algoirthms by Thomas H. Cormen or Algorithms quaternary Edition past times Robert Sedgewick to larn to a greater extent than close them.

Problem statement:  Print nodes of next binary tree inwards postal service order

        45        / \       25  55      / \    \     15  35   65    /   /  \   5   77   88  Output: 5 15 35 25 77 88 65 55 45 
 

Post Order traversal of binary tree inwards Java using Recursion

Let's showtime meet the recursive solution which is extremely tardily to code, especially if you lot know how to impelment pre order  and in order using recursion. All you lot require to exercise is alter the social club of recursive telephone squall upwards according to algorihtm every bit per next steps of postal service social club algorithm.

1) see the left subtree
2) see the correct subtree
3) impress the value of electrical flow node or root.

So inwards instance of given binary tree, nosotros start alongside root(45) as well as and thence become to left, node(25), as well as thence in i trial again nosotros become to left until nosotros accomplish the leafage node 5. At this time, nosotros attempt to become correct subtree now, but in that place is naught in that place thence nosotros impress the value of node. Now, nosotros start to become upwards to node 15, in that place is no correct subtree hither thence nosotros in i trial again impress the value of 15.

Now, nosotros come upwards dorsum to 25, hither nosotros receive got correct subtree thence nosotros become in that place as well as accomplish approximately other leafage node 35, nosotros impress its value as well as comeback to 25, since both xv as well as 35 are visited nosotros impress its value as well as become dorsum to 45. Now nosotros start to correct subtree because left subtree of node 45 is fully explored as well as accomplish to node 55. Since in that place is no left subtree, nosotros become in i trial again to 65, which has left subtree, thence nosotros become to 77 as well as prints its value every bit its a leafage node, nosotros come upwards dorsum to 65 as well as become to correct subtree as well as impress 88 because its leafage node, straightaway nosotros come upwards dorsum in i trial again to 65 as well as prints value.

Similarly nosotros become upwards to 55 as well as since left as well as correct subtree is total explored nosotros prints its value as well as come upwards dorsum to root. Now since both left as well as correct subtree of root is fully visited, nosotros impress the value of root as well as algorithm finished since all nodes are visited.

Here is a post social club implementation inwards Java using recursion:

private void postOrder(TreeNode node) {     if (node == null) {       return;     }      postOrder(node.left);     postOrder(node.right);     System.out.printf("%s ", node.data);   }

The code is just similar to recurive preOrder as well as InOrder algorithm alongside exclusively alter that postOrder() funciton telephone squall upwards is straightaway made for left as well as correct subtree earlier printing value of node. The node == null is nevertheless serve ras base of operations instance of this solution. Btw, if you lot fighting alongside recursion or sympathise recursion but don't know how to come upwards up alongside a recursive algorithm for a problem, I would advise reading Grokking Algorithm, i of the newest majority on the algorithm as well as I guess most readable of all of them.

Binary Tree Post Order Traversal inwards Java without Recursion

The iterative postal service social club traversal algoirthms is the most hard betwen all iii iterative tree traversal algorithm e.g. pre order, inwards social club as well as postal service order. Like other itrative algorithm, nosotros move a Stack to shop nodes. We start alongside root past times pusing it into Stack as well as loop until Stack is empty. In every iteration we peek() the electrical flow node from Stack, recall dissimilar preOrder, nosotros move peek() as well as not pop() method. The peek() method furnish the top of the Stack without removing it. If electrical flow node is Pb node as well as thence nosotros impress its value. Otherwise nosotros cheque electrical flow node has correct as well as left subtree as well as and thence nosotros force those nodes into Stack as well as grade them zero to signify they are already inwards Stack or visited.

Since, nosotros require to see left subtree first, nosotros force the correct node showtime beause Stack is LIFO information construction as well as in conclusion inserted node volition reamin at the top of the stack. nosotros repeat the same procedure until nosotros see all the nodes, at this indicate tree is traversed using postal service social club algorithm. If you lot desire to larn to a greater extent than close Stack as well as how to convert a recursive algorithm to iterative one, delight refer a proficient algorithm majority similar Introduction to Algorithms past times Thomas H. Cormen.

Here is the Java implementation of iterative post-order traversal algorithm of a binary tree:

public void postOrderWithoutRecursion() {     Stack 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;         }       }      }   }

You tin meet that nosotros showtime cheque for leaf node as well as if it's leafage nosotros impress its value. Remember to grade current.left as well as current.right node zero otherwise your computer programme volition never complete as well as code volition become into infinite loop.

Java Program to traverse binary tree inwards postal service social club algorithm

Here is our consummate computer programme to impress all nodes of binary tree every bit per postal service social club traversal inwards Java. You tin too move this algoirthm to collecte all nodes inwards a list, for straightaway nosotros are simply printing. This computer programme implements postal service social club traversal both alongside as well as without recursion. We too move the same BinaryTree as well as TreeNode cast which nosotros receive got used to implement binary search tree, exclusively differnece is that this fourth dimension nosotros receive got non made TreeNode implements Comparable interface. The recursive logic is coded inwards postOrder(TreeNode root) method as well as iterative algorithm is coded into postOrderWithoutRecursion() method.

import java.util.Stack;  /* * Java Program to traverse a binary tree  * using postOrder traversal without recursion.  * In postOrder traversal showtime left subtree is visited, followed past times correct subtree * as well as finally information of root or electrical flow node is printed. *  * input: *       45 *      / \ *     25  55 *    / \    \ *   xv  35   65 *  /   /  \ * v   77   88 *  * output: v xv 35 25 77 88 65 55 45  */  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 using postal service social club traversal using recursion System.out.println("printing nodes of binary tree on postal service social club using recursion");  bt.postOrder();  System.out.println(); // insert novel line  // traversing binary tree on postal service social club traversal without recursion System.out.println("printing nodes of binary tree on postal service social club using iteration"); bt.postOrderWithoutRecursion(); }  }  class BinaryTree { static class TreeNode { String data; TreeNode left, right;  TreeNode(String value) { this.data = value; left = right = null; }  boolean isLeaf() { return left == null ? right == null : false; }  }  // root of binary tree TreeNode root;  /** * traverse the binary tree on postal service social club traversal algorithm */ public void postOrder() { postOrder(root); }  private void postOrder(TreeNode node) { if (node == null) { return; }  postOrder(node.left);  postOrder(node.right); System.out.printf("%s ", node.data); }  public void postOrderWithoutRecursion() { Stack 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 alongside essay information *  * @return a sample binary tree for testing */ public static BinaryTree create() { BinaryTree tree = new BinaryTree(); TreeNode root = new TreeNode("45"); tree.root = root; tree.root.left = new TreeNode("25"); tree.root.left.left = new TreeNode("15"); tree.root.left.left.left = new TreeNode("5");  tree.root.left.right = new TreeNode("35"); tree.root.right = new TreeNode("55"); tree.root.right.right = new TreeNode("65"); tree.root.right.right.left = new TreeNode("77"); tree.root.right.right.right = new TreeNode("88");    return tree; }  }  Output printing nodes of a binary tree on postal service social club using recursion 5 15 35 25 77 88 65 55 45  printing nodes of a binary tree on postal service social club using iteration 5 15 35 25 77 88 65 55 45 

That's all close how to traverse a binary tree inwards postal service order. The recursive postal service social club traversal is pretty tardily but the iterative postal service social club algorithm is quite tough. This too shows indicate that sometime a recursive solution is much to a greater extent than easier as well as readable than iterative i e.g. postal service social club tree travesal or tower of hanoi. The algorithm is unproblematic but its hard to implement using Stack as well as candidate frequently brand error spell coming upwards to tree from leafage node.

Nevertheless this consummate the iii business office serial of articles close binary tree traversal. I am thinking to extend this serial to embrace other tree traversal algorithms e.g. grade social club traversal or spiral leel social club traversal. In the meantime, if you lot desire to relish learning algorithms, you lot tin refer Grokking Algorithms: An illustrated guide for programmers as well as other curious people 1st Edition past times Aditya Bhargava, i of the interesting books on Algorithms alongside lots of existent basis examples as well as a different manner of explanation.

 Other binary tree as well as information construction tutorials you lot may similar to explore

• 5 information construction as well as algorithm books for coding interviews (list)
• How to implement pre-order traversal inwards Java?  (solution)
• How to implement in-order traversal inwards Java? (solution)
• How to impress all leafage nodes of a binary tree inwards Java? (solution)
• How to implement in-order traversal inwards Java without recursion? (solution)
• How to traverse a binary tree inwards pre-order without using recursion? (solution)
• How to impress all leafage nodes of a binary tree without recursion inwards Java? (solution)
• How to implement linked listing using generic inwards Java? (solution)
• How to detect the middle chemical ingredient of linked listing using unmarried pass? (solution)
• How to opposite a singly linked listing inwards Java? (solution)
• How to detect the 3rd chemical ingredient from the halt of linked listing inwards Java? (solution)
• How to opposite an array inwards house inwards Java? (solution)
• How to impress duplicate elements of an array inwards Java? (solution)

Further Learning
Data Structures as well as Algorithms: Deep Dive Using Java
Algorithms as well as Data Structures - Part 1 as well as two
Data Structures inwards Java ix past times Heinz Kabutz

Share this post