Post order traversal of binary tree without recursion

Question

What is the algorithm for doing a post order traversal of a binary tree WITHOUT using recursion

User · Answer

Here s a short  the walker is 3 lines  version that I needed to write in Python for a general tree  Of course  works for a more limited binary tree too  Tree is a tuple of the node and list of children  It only has one stack  Sample usage shown   def postorder tree       def do something x      Your function here         print x       def walk helper root node  calls to perform           calls to perform append partial do something  root node 0            for child in root node 1               calls to perform append partial walk helper  child  calls to perform       calls to perform          calls to perform append partial walk helper  tree  calls to perform       while calls to perform          calls to perform pop     postorder   a      b      c          d                 d   c   b   a

User · Answer

the java version with flag   public static  lt T gt  void printWithFlag TreeNode lt T gt  root       if null    root  return       Stack lt TreeNode lt T gt  gt  stack   new Stack lt TreeNode lt T gt  gt         stack add root        while stack size    gt  0           if stack peek   isVisit                 System out print stack pop   getValue                     else               TreeNode lt T gt  tempNode   stack peek                if tempNode getRight    null                   stack add tempNode getRight                                if tempNode getLeft      null                   stack add tempNode getLeft                                  tempNode setVisit true

User · Answer

The simplest solution  it may look like not the best answer but it is easy to understand  And I believe if you have understood the solution then you can modify it to make the best possible solution     using two stacks  public List lt Integer gt  postorderTraversal TreeNode root     Stack lt TreeNode gt  st new Stack lt  gt      Stack lt TreeNode gt  st2 new Stack lt  gt      ArrayList lt Integer gt  al   new ArrayList lt Integer gt           if root  null          return al    st push root      push the root to 1st stack   while  st isEmpty            TreeNode curr st pop          st2 push curr         if curr left  null          st push curr left        if curr right  null           st push curr right        while  st2 isEmpty        al add st2 pop   val      this ArrayList contains the postorder traversal    return al

User · Answer

Here is the Java implementation with two stacks  public static  lt T gt  List lt T gt  iPostOrder BinaryTreeNode lt T gt  root        if  root    null            return Collections emptyList              List lt T gt  result   new ArrayList lt T gt         Deque lt BinaryTreeNode lt T gt  gt  firstLevel   new LinkedList lt BinaryTreeNode lt T gt  gt         Deque lt BinaryTreeNode lt T gt  gt  secondLevel   new LinkedList lt BinaryTreeNode lt T gt  gt         firstLevel push root       while   firstLevel isEmpty              BinaryTreeNode lt T gt  node   firstLevel pop            secondLevel push node           if  node hasLeftChild                  firstLevel push node getLeft                       if  node hasRightChild                  firstLevel push node getRight                         while   secondLevel isEmpty              result add secondLevel pop   getData                                  return result      Here is the unit tests   Test public void iterativePostOrderTest         BinaryTreeNode lt Integer gt  bst   BinaryTreeUtil  lt Integer gt fromInAndPostOrder new Integer   4 2 5 1 6 3 7   new Integer   4 5 2 6 7 3 1        assertThat BinaryTreeUtil iPostOrder bst  toArray new Integer 0    equalTo new Integer   4 5 2 6 7 3 1

User · Answer

Simple Intuitive solution in python           while stack              node   stack pop               if node                  if isinstance node TreeNode                       stack append node val                      stack append node right                      stack append node left                  else                      post append node          return post

User · Answer

For writing iterative equivalents of these recursive methods  we can first understand how the recursive methods themselves execute over the program s stack  Assuming that the nodes do not have their parent pointer  we need to manage our own  quot stack quot  for the iterative variants  One way to start is to see the recursive method and mark the locations where a call would  quot resume quot   fresh initial call  or after a recursive call returns   Below these are marked as  quot RP 0 quot    quot RP 1 quot  etc   quot Resume Point quot    For the case of postorder traversal  void post node  x             RP 0        if x- gt lc  post x- gt lc          RP 1        if x- gt rc  post x- gt rc          RP 2        process x        Its iterative variant  void post i node  root          node  stack 1000       int top      node  popped        stack 0    root      top   0      popped   NULL       define POPPED A CHILD          popped  amp  amp   popped    curr- gt lc    popped    curr- gt rc         while top  gt   0              node  curr   stack top           if  POPPED A CHILD                       type  x  0             if curr- gt rc    curr- gt lc                      if curr- gt rc  stack   top    curr- gt rc              if curr- gt lc  stack   top    curr- gt lc              popped   NULL            continue                               type  x  2           process curr         top--        popped   curr             The code comments with  x  0  and  x  2  correspond to the  quot RP 0 quot  and  quot RP 2 quot  resume points in the recursive method  By pushing both the lc and rc pointers together  we have removed the need of keeping the post x  invocation at resume-point 1 while the post x- gt lc  completes its execution  That is  we could directly shift the node to  quot RP 2 quot   bypassing  quot RP 1 quot   So  there is no node kept on stack at  quot RP 1 quot  stage  The POPPED A CHILD macro helps us deduce one of the two resume-points   quot RP 0 quot   or  quot RP 2 quot    You can read in detail about this approach here  section  quot Postorder Traversal quot

User · Answer

void display without recursion struct btree   b         deque lt  struct btree   gt  dtree          if  b      dtree push back  b           while  dtree empty                   struct btree  t   dtree front            cout  lt  lt  t- gt nodedata  lt  lt                dtree pop front            if t- gt right          dtree push front t- gt right           if t- gt left          dtree push front t- gt left             cout  lt  lt  endl

User · Answer

Here s the version with one stack and without a visited flag   private void postorder Node head      if  head    null        return        LinkedList lt Node gt  stack   new LinkedList lt Node gt       stack push head      while   stack isEmpty          Node next   stack peek         boolean finishedSubtrees    next right    head    next left    head       boolean isLeaf    next left    null  amp  amp  next right    null       if  finishedSubtrees    isLeaf          stack pop          System out println next value         head   next            else         if  next right    null            stack push next right                 if  next left    null            stack push next left

User · Answer

Two methods to perform Post Order Traversal without Recursion   1  Using One HashSet of Visited Nodes and One stack for backtracking   private void postOrderWithoutRecursion TreeNode root        if  root    null    root left    null  amp  amp  root right    null            return            Stack lt TreeNode gt  stack   new Stack lt  gt         Set lt TreeNode gt  visited   new HashSet lt  gt         while   stack empty      root    null            if  root    null                stack push root               visited add root               root   root left            else               root   stack peek                if  root right    null    visited contains root right                     System out print root val                       stack pop                    root   null                else                   root   root right                                      Time Complexity  O n   Space Complexity  O 2n    2  Using Tree Altering method    private void postOrderWithoutRecursionAlteringTree TreeNode root        if  root    null    root left    null  amp  amp  root right    null            return            Stack lt TreeNode gt  stack   new Stack lt  gt         while   stack empty      root    null            if  root    null                stack push root               root   root left            else               root   stack peek                if  root right    null                    System out print root val                       stack pop                    root   null                else                   TreeNode temp   root right                  root right   null                  root   temp                                     Time Complexity  O n   Space Complexity  O n    TreeNode Class   public class TreeNode       public int val       public TreeNode left       public TreeNode right       public TreeNode int x            val   x

User · Answer

In post-order traversal  he left child of a node is visited first  followed by its right child  and finally the node itself  This tree traversal method is similar to depth first search  DFS  traversal of a graph  Time Complexity   O n  Space Complexity  O n  Below is the iterative implementation of post-order traversal in python  class Node      def   init   self  data None  left None  right None           self data    data         self left    left         self right   right  def post order node       if node is None          return        stack          nodes          last node visited   None     while stack or node          if node              stack append node              node   node left         else              peek node   stack -1              if peek node right and last node visited    peek node right                  node   peek node right             else                  nodes append peek node data                  last node visited   stack pop       return nodes  def main                Construct the below binary tree               15                                                            10      20                           8   12  16  25              root   Node 15      root left    Node 10      root right   Node 20      root left left    Node 8      root left right   Node 12      root right left    Node 16      root right right   Node 25      print post order root     if   name         main         main

User · Answer

Here is a solution in C   that does not require any storage for book keeping in the tree  Instead it uses two stacks  One to help us traverse and another to store the nodes so we can do a post traversal of them   std  stack lt Node  gt  leftStack  std  stack lt Node  gt  rightStack   Node  currentNode   m root  while   leftStack empty      currentNode    NULL         if  currentNode                 leftStack push  currentNode            currentNode   currentNode- gt m left            else               currentNode   leftStack top            leftStack pop             rightStack push  currentNode            currentNode   currentNode- gt m right           while   rightStack empty           currentNode   rightStack top        rightStack pop         std  cout  lt  lt  currentNode- gt m value      std  cout  lt  lt    n

User · Answer

This code will ensure holding of chain links  of nodes from the root to till the level of the tree     The number of extra nodes in the memory  other than tree  is height of the tree     I haven t used java stack instead used this ParentChain      This parent chain is the link for any node from the top root node  to till its immediate parent     This code will not require any altering of existing BinaryTree  NO flag parent on all the nodes            while visiting the Node 11  ParentChain will be holding the nodes 9 - gt  8 - gt  7 - gt  1 where  - gt  is parent                      1                                                                                                                                                                                                                                                                                                               2               7                                                                                                                                                       3       6       8                                                                                   4   5           9                                                                 10 11                        author ksugumar        public class InOrderTraversalIterative       public static void main String   args            BTNode lt String gt  rt          String   dataArray     1   2   3   4  null null  5  null null  6  null null  7   8   9   10  null null  11  null null null null           rt   BTNode buildBTWithPreOrder dataArray  new Counter 0            BTDisplay printTreeNode rt           inOrderTravesal rt          public static void postOrderTravesal BTNode lt String gt  root        ParentChain rootChain   new ParentChain root       rootChain Parent   new ParentChain null        while  root    null               Going back to parent         if rootChain leftVisited  amp  amp  rootChain rightVisited                System out println root data     Visit the node              ParentChain parentChain   rootChain Parent              rootChain Parent   null    Avoid the leak             rootChain   parentChain              root   rootChain root              continue                       Traverse Left         if  rootChain leftVisited                rootChain leftVisited   true              if  root left    null                    ParentChain local   new ParentChain root left     It is better to use pool to reuse the instances                  local Parent   rootChain                  rootChain   local                  root   root left                  continue                                      Traverse RIGHT         if  rootChain rightVisited                rootChain rightVisited   true              if  root right    null                    ParentChain local   new ParentChain root right     It is better to use pool to reuse the instances                  local Parent   rootChain                  rootChain   local                  root   root right                  continue                                   class ParentChain       BTNode lt String gt  root      ParentChain Parent      boolean leftVisited   false      boolean rightVisited   false       public ParentChain BTNode lt String gt  node            this root   node               Override     public String toString             return root toString

User · Answer

I have not added the node class as its not particularly relevant or any test cases  leaving those as an excercise for the reader etc   void postOrderTraversal node  root        if root    NULL          return       stack lt node  gt  st      st push root          store most recent  visited  node     node  prev root       while st size    gt  0                node  top   st top            if  top- gt left    NULL  amp  amp  top- gt right    NULL                         prev   top              cerr lt  lt top- gt val lt  lt                  st pop                continue                    else                         we can check if we are going back up the tree if the current               node has a left or right child that was previously outputted             if  top- gt left    prev      top- gt right   prev                                 prev   top                  cerr lt  lt top- gt val lt  lt                      st pop                    continue                             if top- gt right    NULL                  st push top- gt right                if top- gt left    NULL                  st push top- gt left                       cerr lt  lt endl      running time O n  - all nodes need to be visited AND space O n  - for the stack  worst case tree is a single line linked list

User · Answer

Please see this full Java implementation  Just copy the code and paste in your compiler  It will work fine    import java util LinkedList  import java util Queue  import java util Stack   class Node       Node left      String data      Node right       Node Node left  String data  Node right                this left   left          this right   right          this data   data             public String getData                 return data           class Tree       Node node         insert     public void insert String data                if node    null              node   new Node null data null           else                       Queue lt Node gt  q   new LinkedList lt Node gt                 q add node                while q peek      null                                Node temp   q remove                    if temp left    null                                        temp left   new Node null data null                       break                                    else                                       q add temp left                                      if temp right    null                                        temp right   new Node null data null                       break                                    else                                       q add temp right                                                        public void postorder Node node                if node    null              return          postorder node left           postorder node right           System out print node getData     -- gt                 public void iterative Node node                Stack lt Node gt  s   new Stack lt Node gt             while true                        while node    null                                s push node                   node   node left                               if s peek   right    null                                node   s pop                    System out print node getData     -- gt                      if node    s peek   right                                        System out print s peek   getData     -- gt                          s pop                                                 if s isEmpty                    break               if s peek      null                                node   s peek   right                            else                               node   null                                   class Main       public static void main String   args                 Tree t   new Tree            t insert  A            t insert  B            t insert  C            t insert  D            t insert  E             t postorder t node           System out println             t iterative t node           System out println

User · Answer

I was looking for a code snippet that performs well and is simple to customise  Threaded trees are not    simple     Double stack solution requires O n  memory  LeetCode solution and solution by tcb have extra checks and pushes      Here is one classic algorithm translated into C that worked for me   void postorder traversal TreeNode  p  void   visit  TreeNode           TreeNode    stack 40           simple C stack  no overflow check     TreeNode    sp   stack      TreeNode    last visited   NULL       for    p    NULL  p   p- gt left           sp     p       while  sp    stack            p   sp -1           if  p- gt right    NULL    p- gt right    last visited                visit p               last visited   p              sp--            else               for  p   p- gt right  p    NULL  p   p- gt left                   sp     p                      IMHO this algorithm is easier to follow than well performing and readable wikipedia org   Tree traversal pseudocode  For glorious details see answers to binary tree exercises in Knuth   s Volume 1

User · Answer

Here s a link which provides two other solutions without using any visited flags   https   leetcode com problems binary-tree-postorder-traversal   This is obviously a stack-based solution due to the lack of parent pointer in the tree   We wouldn t need a stack if there s parent pointer    We would push the root node to the stack first  While the stack is not empty  we keep pushing the left child of the node from top of stack  If the left child does not exist  we push its right child  If it s a leaf node  we process the node and pop it off the stack   We also use a variable to keep track of a previously-traversed node  The purpose is to determine if the traversal is descending ascending the tree  and we can also know if it ascend from the left right   If we ascend the tree from the left  we wouldn t want to push its left child again to the stack and should continue ascend down the tree if its right child exists  If we ascend the tree from the right  we should process it and pop it off the stack   We would process the node and pop it off the stack in these 3 cases    The node is a leaf node  no children  We just traverse up the tree from the left and no right child exist  We just traverse up the tree from the right

User · Answer

So you can use one stack to do a post order traversal   private void PostOrderTraversal Node pos        Stack lt Node gt  stack   new Stack lt Node gt         do           if  pos  null  amp  amp   pos stack peek   right   null                for  visit stack peek     stack pop     stack isEmpty   null stack peek   right   visit stack peek                  else if pos  null                stack push pos               pos pos left                  while   stack isEmpty

User · Answer

The logic of Post order traversal without using Recursion In Postorder traversal  the processing order is left-right-current  So we need to visit the left section first before visiting other parts  We will try to traverse down to the tree as left as possible for each node of the tree  For each current node  if the right child is present then push it into the stack before pushing the current node while root is not NULL None  Now pop a node from the stack and check whether the right child of that node exists or not  If it exists  then check whether it s same as the top element or not  If they are same then it indicates that we are not done with right part yet  so before processing the current node we have to process the right part and for that pop the top element right child  and push the current node back into the stack  At each time our head is the popped element  If the current element is not the same as the top and head is not NULL then we are done with both the left and right section so now we can process the current node  We have to repeat the previous steps until the stack is empty  def Postorder iterative head       if head is None          return None     sta stack       while True          while head is not None              if head r                  sta push head r              sta push head              head head l         if sta top is -1              break         head   sta pop           if head r is not None and sta top is not -1  and head r is sta A sta top               x sta pop               sta push head              head x         else              print head val end                    head None     print

User · Answer

Here s a sample from wikipedia   nonRecursivePostorder rootNode    nodeStack push rootNode    while    nodeStack empty        currNode   nodeStack peek       if   currNode left    null  and  currNode left visited    false         nodeStack push currNode left      else        if   currNode right    null  and  currNode right visited    false           nodeStack push currNode right        else         print currNode value         currNode visited    true         nodeStack pop

User · Answer

import java util Stack     class Practice        public static void main String arr                  Practice prc   new Practice            TreeNode node1    prc  new TreeNode 1           TreeNode node2    prc  new TreeNode 2           TreeNode node3    prc  new TreeNode 3           TreeNode node4    prc  new TreeNode 4           TreeNode node5    prc  new TreeNode 5           TreeNode node6    prc  new TreeNode 6           TreeNode node7    prc  new TreeNode 7           node1 left   node2          node1 right   node3          node2 left   node4          node2 right   node5          node3 left   node6          node3 right   node7          postOrderIteratively node1              public static void postOrderIteratively TreeNode root                Stack lt Entry gt  stack   new Stack lt Entry gt             Practice prc   new Practice            stack push  prc  new Entry root  false            while   stack isEmpty                          Entry entry   stack pop                TreeNode node   entry node              if  entry flag    false                                if  node right    null  amp  amp  node left    null                                        System out println node data                     else                                       stack push  prc  new Entry node  true                        if  node right    null                                                stack push  prc  new Entry node right  false                                              if  node left    null                                                stack push  prc  new Entry node left  false                                                          else                               System out println node data                                       class TreeNode               int data          int leafCount          TreeNode left          TreeNode right           public TreeNode int data                        this data   data                     public int getLeafCount                         return leafCount                     public void setLeafCount int leafCount                        this leafCount   leafCount                     public TreeNode getLeft                         return left                     public void setLeft TreeNode left                        this left   left                     public TreeNode getRight                         return right                     public void setRight TreeNode right                        this right   right                      Override         public String toString                         return      this data                       class Entry               Entry TreeNode node  boolean flag                        this node   node              this flag   flag                     TreeNode node          boolean flag            Override         public String toString                         return node toString

User · Answer

It s very nice to see so many spirited approaches to this problem  Quite inspiring indeed   I came across this topic searching for a simple iterative solution for deleting all nodes in my binary tree implementation  I tried some of them  and I tried something similar found elsewhere on the Net  but none of them were really to my liking   The thing is  I am developing a database indexing module for a very specific purpose  Bitcoin Blockchain indexing   and my data is stored on disk  not in RAM  I swap in pages as needed  doing my own memory management  It s slower  but fast enough for the purpose  and with having storage on disk instead of RAM  I have no religious bearings against wasting space  hard disks are cheap    For that reason my nodes in my binary tree have parent pointers  That s  all  the extra space I m talking about  I need the parents because I need to iterate both ascending and descending through the tree for various purposes   Having that in my mind  I quickly wrote down a little piece of pseudo-code on how it could be done  that is  a post-order traversal deleting nodes on the fly  It s implemented and tested  and became a part of my solution  And it s pretty fast too   The thing is  It gets really  REALLY  simple when nodes have parent pointers  and furthermore since I can null out the parent s link to the  just departed  node   Here s the pseudo-code for iterative post-order deletion   Node current   root  while  current      if  current left        current   current left      Dive down left   else if  current right  current   current right     Dive down right   else            Node  current  is a leaf  i e  no left or right child     Node parent   current parent     assuming root parent    null     if  parent                 Null out the parent s link to the just departing node       if  parent left    current  parent left   null        else                        parent right   null            delete current      current   parent        root   null    If you are interested in a more theoretical approach to coding complex collections  such as my binary tree  which is really a self-balancing red-black-tree   then check out these links   http   opendatastructures org versions edition-0 1e ods-java 6 2 BinarySearchTree Unbala html http   opendatastructures org versions edition-0 1e ods-java 9 2 RedBlackTree Simulated  html https   www cs auckland ac nz software AlgAnim red black html  Happy coding  -   S  ren Fog http   iprotus eu

User · Answer

This is the approach I use for iterative  post-order traversal  I like this approach because    It only handles a single transition per loop-cycle  so it s easy to follow  A similar solution works for in-order and pre-order traversals   Code   enum State  LEFT  RIGHT  UP  CURR   public void iterativePostOrder Node root      Deque lt Node gt  parents   new ArrayDeque lt  gt       Node   curr   root    State state   State LEFT     while   curr    root  amp  amp  state    State UP         switch state          case LEFT          if curr left    null              parents push curr             curr   curr left            else             state   RIGHT                    break        case RIGHT          if curr right    null              parents push curr             curr   curr right            state   LEFT            else             state   CURR                    break         case CURR          System out println curr           state   UP          break        case UP           Node child   curr          curr   parents pop            state   child    curr left   RIGHT   CURR          break        default          throw new IllegalStateException                  Explanation   You can think about the steps like this    Try LEFT   if left-node exists  Try LEFT again if left-node does not exist  Try RIGHT  Try RIGHT   If a right node exists  Try LEFT from there If no right exists  you re at a leaf  Try CURR  Try CURR   Print current node All nodes below have been executed  post-order   Try UP  Try UP   If node is root  there is no UP  so EXIT If coming up from left  Try RIGHT If coming up from right  Try CURR

User · Answer

Here is a Python version too      class Node      def   init   self data           self data   data         self left   None         self right   None  def postOrderIterative root        if root is None           return      s1          s2          s1 append root       while len s1  gt 0           node   s1 pop           s2 append node           if node left  None               s1 append node left           if node right  None               s1 append node right       while len s2  gt 0           node   s2 pop           print node data   root   Node 1  root left   Node 2  root right   Node 3  root left left   Node 4  root left right   Node 5  root right left   Node 6  root right right   Node 7  postOrderIterative root    Here is the output

User · Answer

void postorder stack Node   root       stack ms      ms top   -1      if root    NULL  return        Node   temp       push  amp ms root       Node   prev   NULL      while  is empty ms            temp   peek ms              case 1  We are nmoving down the tree             if prev    NULL    prev- gt left    temp    prev- gt right    temp                if temp- gt left                    push  amp ms temp- gt left                else if temp- gt right                    push  amp ms temp- gt right                else                      If node is leaf node                       printf   d    temp- gt value                      pop  amp ms                                         case 2  We are moving up the tree from left child             if temp- gt left    prev                 if temp- gt right                     push  amp ms temp- gt right                 else                    printf   d    temp- gt value                          case 3  We are moving up the tree from right child             if temp- gt right    prev                 printf   d    temp- gt value                 pop  amp ms                       prev   temp

User · Answer

Python with 1 stack and no flag   def postorderTraversal self  root       ret          if not root          return ret     stack    root      current   None     while stack          previous   current         current   stack pop           if previous and   previous is current  or  previous is current left  or  previous is current right                ret append current val          else              stack append current              if current right                  stack append current right              if current left                  stack append current left       return ret   And what is better is with similar statements  in order traversal works too  def inorderTraversal self  root       ret          if not root          return ret     stack    root      current   None     while stack          previous   current         current   stack pop           if None    previous or previous left is current or previous right is current              if current right                  stack append current right              stack append current              if current left                  stack append current left          else              ret append current val       return ret

User · Answer

This is what I ve come up for post order iterator      class PostOrderIterator     implements Iterator lt T gt             private Stack lt Node lt T gt  gt  stack          private Node lt T gt  prev           PostOrderIterator Node lt T gt  root                this stack   new Stack lt  gt                 recurse root               this prev   this stack peek                       private void recurse Node lt T gt  node                if node    null                    return                             while node    null                    stack push node                   node   node left                            recurse stack peek   right                       Override         public boolean hasNext                 return  stack isEmpty                        Override         public T next                 if stack peek   right    this prev                    recurse stack peek   right                              Node lt T gt  next   stack pop                this prev   next              return next value                   Basically  the main idea is that you should think how the initialization process puts the first item to print on the top of the stack  while the rest of the stack follow the nodes that would have been touched by the recursion  The rest would just then become a lot easier to nail  Also  from design perspective  PostOrderIterator is an internal class exposed via some factory method of the tree class as an Iterator lt T gt

User · Answer

1 1 Create an empty stack  2 1 Do following while root is not NULL  a  Push root s right child and then root to stack   b  Set root as root s left child    2 2 Pop an item from stack and set it as root   a  If the popped item has a right child and the right child     is at top of stack  then remove the right child from stack     push the root back and set root as root s right child   b  Else print root s data and set root as NULL    2 3 Repeat steps 2 1 and 2 2 while stack is not empty

User · Answer

Depth first  post order  non recursive  without stack  When you have parent      node t           left       right      parent          traverse node t rootNode            bool backthreading   false       node t node   rootNode       while node  lt  gt  0           if  node- gt left  lt  gt  0  and backthreading   false then                node   node- gt left              continue          endif            gt  gt  gt  process node here  lt  lt  lt            if node- gt right  lt  gt  0 then             lNode   node- gt right             backthreading   false         else             node   node- gt parent              backthreading   true         endif     endwhile

User · Answer

import java util Stack   public class IterativePostOrderTraversal extends BinaryTree        public static void iterativePostOrderTraversal Node root           Node cur   root          Node pre   root          Stack lt Node gt  s   new Stack lt Node gt             if root  null              s push root           System out println  sysout  s isEmpty             while  s isEmpty                 cur   s peek                if cur  pre  cur  pre left   cur  pre right     we are traversing down the tree                 if cur left  null                       s push cur left                                     else if cur right  null                       s push cur right                                     if cur left  null  amp  amp  cur right  null                       System out println s pop   data                                  else if pre  cur left     we are traversing up the tree from the left                 if cur right  null                       s push cur right                    else if cur right  null                       System out println s pop   data                                  else if pre  cur right     we are traversing up the tree from the right                 System out println s pop   data                             pre cur                       public static void main String args             BinaryTree bt   new BinaryTree            Node root   bt generateTree            iterativePostOrderTraversal root

User · Answer

Here I am pasting different versions in c    net  for reference   for in-order iterative traversal you may refer to  Help me understand Inorder Traversal without using recursion    wiki  http   en wikipedia org wiki Post-order 5Ftraversal Implementations   elegant  Another version of single stack   1 and  2  basically uses the fact that in post order traversal the right child node is visited before visiting the actual node - so  we simply rely on the check that if stack top s right child is indeed the last post order traversal node thats been visited - i have added comments in below code snippets for details   Using Two stacks version  ref  http   www geeksforgeeks org iterative-postorder-traversal     easier  basically post order traversal reverse is nothing but pre order traversal with a simple tweak that right node is visited first  and then left node  Using visitor flag  easy  Unit Tests      public string PostOrderIterative WikiVersion                         List lt int gt  nodes   new List lt int gt                 if  null    this  root                                BinaryTreeNode lastPostOrderTraversalNode   null                  BinaryTreeNode iterativeNode   this  root                  Stack lt BinaryTreeNode gt  stack   new Stack lt BinaryTreeNode gt                     while   stack Count  gt  0   stack is not empty                         iterativeNode    null                                         if  iterativeNode    null                                                stack Push iterativeNode                           iterativeNode   iterativeNode Left                                            else                                               var stackTop   stack Peek                            if  stackTop Right    null                               amp  amp   stackTop Right    lastPostOrderTraversalNode                                                           i e  last traversal node is not right element  so right sub tree is not                               yet  traversed  so we need to start iterating over right tree                                 note left tree is by default traversed by above case                              iterativeNode   stackTop Right                                                    else                                                         if either the iterative node is child node  right and left are null                                or  stackTop s right element is nothing but the last traversal node                                i e  the element can be popped as the right sub tree have been traversed                              var top   stack Pop                                Debug Assert top    stackTop                               nodes Add top Element                               lastPostOrderTraversalNode   top                                                                                              return this ListToString nodes               Here is post order traversal with one stack  my version   public string PostOrderIterative                         List lt int gt  nodes   new List lt int gt                 if  null    this  root                                BinaryTreeNode lastPostOrderTraversalNode   null                  BinaryTreeNode iterativeNode   null                  Stack lt BinaryTreeNode gt  stack   new Stack lt BinaryTreeNode gt                     stack Push this  root                   while stack Count  gt  0                                        iterativeNode   stack Pop                        if   iterativeNode Left    null                           amp  amp   iterativeNode Right    null                                                 nodes Add iterativeNode Element                           lastPostOrderTraversalNode   iterativeNode                            make sure the stack is not empty as we need to peek at the top                           for ex  a tree with just root node doesn t have to enter loop                           and also node Peek   will throw invalidoperationexception                           if it is performed if the stack is empty                           so  it handles both of them                          while stack Count  gt  0                                                         var stackTop   stack Peek                                bool removeTop   false                              if   stackTop Right    null   amp  amp                                    i e  last post order traversal node is nothing but right node of                                    stacktop  so  all the elements in the right subtree have been visted                                   So  we can pop the top element                                  stackTop Right    lastPostOrderTraversalNode                                                                   in other words  we can pop the top if whole right subtree is                                   traversed  i e  last traversal node should be the right node                                   as the right node will be traverse once all the subtrees of                                   right node has been traversed                                 removeTop   true                                                            else if                                    right subtree is null                                  stackTop Right    null                                    amp  amp   stackTop Left    null                                     last traversal node is nothing but the root of left sub tree node                                  amp  amp   stackTop Left    lastPostOrderTraversalNode                                                                   in other words  we can pop the top of stack if right subtree is null                                    and whole left subtree has been traversed                                 removeTop   true                                                            else                                                               break                                                            if removeTop                                                                var top   stack Pop                                    Debug Assert stackTop    top                                   lastPostOrderTraversalNode   top                                  nodes Add top Element                                                                                                     else                                                stack Push iterativeNode                           if iterativeNode Right    null                                                        stack Push iterativeNode Right                                                     if iterativeNode Left    null                                                        stack Push iterativeNode Left                                                                                               return this ListToString nodes               Using two stacks  public string PostOrderIterative TwoStacksVersion                         List lt int gt  nodes   new List lt int gt                 if  null    this  root                                Stack lt BinaryTreeNode gt  postOrderStack   new Stack lt BinaryTreeNode gt                     Stack lt BinaryTreeNode gt  rightLeftPreOrderStack   new Stack lt BinaryTreeNode gt                     rightLeftPreOrderStack Push this  root                   while rightLeftPreOrderStack Count  gt  0                                        var top   rightLeftPreOrderStack Pop                        postOrderStack Push top                       if top Left    null                                                rightLeftPreOrderStack Push top Left                                             if top Right    null                                                rightLeftPreOrderStack Push top Right                                                           while postOrderStack Count  gt  0                                        var top   postOrderStack Pop                        nodes Add top Element                                               return this ListToString nodes               With visited flag in C    net    public string PostOrderIterative                         List lt int gt  nodes   new List lt int gt                 if  null    this  root                                BinaryTreeNode iterativeNode   null                  Stack lt BinaryTreeNode gt  stack   new Stack lt BinaryTreeNode gt                     stack Push this  root                   while stack Count  gt  0                                        iterativeNode   stack Pop                        if iterativeNode visted                                                  reset the flag  for further traversals                         iterativeNode visted   false                          nodes Add iterativeNode Element                                             else                                               iterativeNode visted   true                          stack Push iterativeNode                           if iterativeNode Right    null                                                        stack Push iterativeNode Right                                                     if iterativeNode Left    null                                                        stack Push iterativeNode Left                                                                                               return this ListToString nodes               The definitions   class BinaryTreeNode               public int Element          public BinaryTreeNode Left          public BinaryTreeNode Right          public bool visted         string ListToString List lt int gt  list                        string s   string Join       list               return s              Unit Tests   TestMethod          public void PostOrderTests                         int   a     13  2  18  1  5  17  20  3  6  16  21  4  14  15  25  22  24                BinarySearchTree bst   new BinarySearchTree                foreach  int e in a                                string s1   bst PostOrderRecursive                    string s2   bst PostOrderIterativeWithVistedFlag                    string s3   bst PostOrderIterative                    string s4   bst PostOrderIterative WikiVersion                    string s5   bst PostOrderIterative TwoStacksVersion                    Assert AreEqual s1  s2                   Assert AreEqual s2  s3                   Assert AreEqual s3  s4                   Assert AreEqual s4  s5                   bst Add e                   bst Delete e                   bst Add e                   s1   bst PostOrderRecursive                    s2   bst PostOrderIterativeWithVistedFlag                    s3   bst PostOrderIterative                    s4   bst PostOrderIterative WikiVersion                    s5   bst PostOrderIterative TwoStacksVersion                    Assert AreEqual s1  s2                   Assert AreEqual s2  s3                   Assert AreEqual s3  s4                   Assert AreEqual s4  s5                             Debug WriteLine string Format  PostOrderIterative   0    bst PostOrderIterative                  Debug WriteLine string Format  PostOrderIterative WikiVersion   0    bst PostOrderIterative WikiVersion                  Debug WriteLine string Format  PostOrderIterative TwoStacksVersion   0    bst PostOrderIterative TwoStacksVersion                  Debug WriteLine string Format  PostOrderIterativeWithVistedFlag   0    bst PostOrderIterativeWithVistedFlag                  Debug WriteLine string Format  PostOrderRecursive   0    bst PostOrderRecursive

[binary-tree] Post order traversal of binary tree without recursion

Examples related to binary-tree

Examples related to traversal

Examples related to non-recursive