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?

Solution 1

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:

1. The node is a leaf node (no children)
2. We just traverse up the tree from the left and no right child exist.
3. We just traverse up the tree from the right.

Solution 2

Here's the version with one stack and without a visited flag:

private void postorder(Node head) {
  if (head == null) {
    return;
  }
  LinkedList<Node> stack = new LinkedList<Node>();
  stack.push(head);

  while (!stack.isEmpty()) {
    Node next = stack.peek();

    boolean finishedSubtrees = (next.right == head || next.left == head);
    boolean isLeaf = (next.left == null && 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);
      }
    }
  }
}

Solution 3

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()

Solution 4

This is the approach I use for iterative, post-order traversal. I like this approach because:

1. It only handles a single transition per loop-cycle, so it's easy to follow.
2. A similar solution works for in-order and pre-order traversals

Code:

enum State {LEFT, RIGHT, UP, CURR}

public void iterativePostOrder(Node root) {
  Deque<Node> parents = new ArrayDeque<>();
  Node   curr = root;
  State state = State.LEFT;

  while(!(curr == root && 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:

1. Try LEFT
   • if left-node exists: Try LEFT again
   • if left-node does not exist: Try RIGHT
2. Try RIGHT
   • If a right node exists: Try LEFT from there
   • If no right exists, you're at a leaf: Try CURR
3. Try CURR
   • Print current node
   • All nodes below have been executed (post-order): Try UP
4. 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

Solution 5

// the java version with flag

public static <T> void printWithFlag(TreeNode<T> root){
    if(null == root) return;

    Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();
    stack.add(root);

    while(stack.size() > 0){
        if(stack.peek().isVisit()){
            System.out.print(stack.pop().getValue() + "  ");
        }else{

            TreeNode<T> tempNode = stack.peek();
            if(tempNode.getRight()!=null){
                stack.add(tempNode.getRight());
            }

            if(tempNode.getLeft() != null){
                stack.add(tempNode.getLeft());
            }



            tempNode.setVisit(true);


        }
    }
}

View more solutions

Comments

[Flethuseo]

You have a bug in your code: try 'abcdefghi' and it loops forever

[Flethuseo]

To fix the bug I changed the 'if (node == s.peek().right)' with ---> while (!s.isEmpty() && node == s.peek().right)

[Kanagavelu Sugumar]

github.com/skanagavelu/Algorithams/blob/master/src/tree/…

[Charlie 木匠]

This solution is easy to understand. -- The wiki implementation code changed. ^_^ . en.wikipedia.org/wiki/Tree_traversal#Post-order

[Nicolas]

I could use an explanation too. How could next.left or next.right ever equal head? And how does that indicate you finished subtrees? And what does finished subtrees mean?

[vaughnkoch]

The alg visits each node and puts its children on the stack until it reaches a leaf node. It prints the leaf and temporarily points 'head' to that node. Then, once it's printed the leaves and popped them off the stack, it returns to the parent node and sees whether any of the subtrees has been visited. If any of the children is 'head', that means at least one subtree has been fully printed. Also, since a parent is always lower than its children, all subtrees have been visited. The preorder traversal comes from the fact that it's printing the leaf nodes first, and preferentially the left node.

[Samuel Li]

Wow, this is easy to follow and flexible to modify, nice!

[Ciro Santilli OurBigBook.com]

It could also be good to keep children in an array or list, this way you can do: finishedSubtrees = next.right == head and isLeaf = next.length == 0`. This also generalizes directly to non-binary trees.