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?

Amedeo

Here is a great description: geeksforgeeks.org/iterative-postorder-traversal-using-stack – Restoration

Answer 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.

Spangler

Answer 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);
      }
    }
  }
}

Kavita

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? – Speer

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. – Undervalue

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. – Fredericksburg

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

Linear

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

Answer 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

Menken

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

Answer 5

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<Node*> leftStack;
std::stack<Node*> rightStack;

Node* currentNode = m_root;
while( !leftStack.empty() || currentNode != NULL )
{
    if( currentNode )
    {
        leftStack.push( currentNode );
        currentNode = currentNode->m_left;
    }
    else
    {
        currentNode = leftStack.top();
        leftStack.pop();

        rightStack.push( currentNode );
        currentNode = currentNode->m_right;
    }
}

while( !rightStack.empty() )
{
    currentNode = rightStack.top();
    rightStack.pop();

    std::cout << currentNode->m_value;
    std::cout << "\n";
}

Slideaction

Answer 6

import java.util.Stack;

public class IterativePostOrderTraversal extends BinaryTree {

    public static void iterativePostOrderTraversal(Node root){
        Node cur = root;
        Node pre = root;
        Stack<Node> s = new Stack<Node>();
        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 && 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);
    }


}

Chism

Answer 7

// 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);


        }
    }
}

Doublethink

Answer 8

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

        if (node->left <> 0) and backthreading = false then
               node = node->left

            continue 
        endif

         >>> process node here <<<


        if node->right <> 0 then
            lNode = node->right
            backthreading = false
        else
            node = node->parent

            backthreading = true
        endif
    endwhile

Gauger

Answer 9

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

Entertain

Answer 10

void postorder_stack(Node * root){
    stack ms;
    ms.top = -1;
    if(root == NULL) return ;

    Node * temp ;
    push(&ms,root);
    Node * prev = NULL;
    while(!is_empty(ms)){
        temp = peek(ms);
        /* case 1. We are nmoving down the tree. */
        if(prev == NULL || prev->left == temp || prev->right == temp){
             if(temp->left)
                  push(&ms,temp->left);
             else if(temp->right)
                  push(&ms,temp->right);
             else {
                /* If node is leaf node */
                   printf("%d ", temp->value);
                   pop(&ms);
             }
         }
         /* case 2. We are moving up the tree from left child */
         if(temp->left == prev){
              if(temp->right)
                   push(&ms,temp->right);
              else
                   printf("%d ", temp->value);
         }

        /* case 3. We are moving up the tree from right child */
         if(temp->right == prev){
              printf("%d ", temp->value);
              pop(&ms);
         }
         prev = temp;
      }

}

Henleyonthames

Answer 11

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<Node> q = new LinkedList<Node>();
            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()+" --> ");
    }

    public void iterative(Node node)
    {
        Stack<Node> s = new Stack<Node>();
        while(true)
        {
            while(node != null)
            {
                s.push(node);
                node = node.left;
            }



            if(s.peek().right == null)
            {
                node = s.pop();
                System.out.print(node.getData()+" --> ");
                if(node == s.peek().right)
                {
                    System.out.print(s.peek().getData()+" --> ");
                    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();
    }
}

Cleopatracleopatre

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

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

Answer 12

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)

1. wiki (http://en.wikipedia.org/wiki/Post-order%5Ftraversal#Implementations) (elegant)
2. 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)
3. 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)
4. Using visitor flag (easy)
5. Unit Tests

~

public string PostOrderIterative_WikiVersion()
        {
            List<int> nodes = new List<int>();
            if (null != this._root)
            {
                BinaryTreeNode lastPostOrderTraversalNode = null;
                BinaryTreeNode iterativeNode = this._root;
                Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
                while ((stack.Count > 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)
                            && (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<int> nodes = new List<int>();
            if (null != this._root)
            {
                BinaryTreeNode lastPostOrderTraversalNode = null;
                BinaryTreeNode iterativeNode = null;
                Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
                stack.Push(this._root);
                while(stack.Count > 0)
                {
                    iterativeNode = stack.Pop();
                    if ((iterativeNode.Left == null)
                        && (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 > 0) 
                        {
                            var stackTop = stack.Peek();
                            bool removeTop = false;
                            if ((stackTop.Right != null) &&
                                //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) 
                                && (stackTop.Left != null) 
                                //last traversal node is nothing but the root of left sub tree node
                                && (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<int> nodes = new List<int>();
            if (null != this._root)
            {
                Stack<BinaryTreeNode> postOrderStack = new Stack<BinaryTreeNode>();
                Stack<BinaryTreeNode> rightLeftPreOrderStack = new Stack<BinaryTreeNode>();
                rightLeftPreOrderStack.Push(this._root);
                while(rightLeftPreOrderStack.Count > 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 > 0)
                {
                    var top = postOrderStack.Pop();
                    nodes.Add(top.Element);
                }
            }
            return this.ListToString(nodes);
        }

With visited flag in C# (.net):

public string PostOrderIterative()
        {
            List<int> nodes = new List<int>();
            if (null != this._root)
            {
                BinaryTreeNode iterativeNode = null;
                Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
                stack.Push(this._root);
                while(stack.Count > 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<int> 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()));
        }

Ivon

Answer 13

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

Pantoja

Answer 14

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<node*> st;
    st.push(root);

    //store most recent 'visited' node
    node* prev=root;

    while(st.size() > 0)
    {
        node* top = st.top();
        if((top->left == NULL && top->right == NULL))
        {
            prev = top;
            cerr<<top->val<<" ";
            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->left == prev) || (top->right== prev))
            {
                prev = top;
                cerr<<top->val<<" ";
                st.pop();
                continue;
            }

            if(top->right != NULL)
                st.push(top->right);

            if(top->left != NULL)
                st.push(top->left);
        }
    }
    cerr<<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

Luteolin

Answer 15

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/

Tunnel

Answer 16

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.

Vines

Answer 17

Here is the Java implementation with two stacks

public static <T> List<T> iPostOrder(BinaryTreeNode<T> root) {
    if (root == null) {
        return Collections.emptyList();
    }
    List<T> result = new ArrayList<T>();
    Deque<BinaryTreeNode<T>> firstLevel = new LinkedList<BinaryTreeNode<T>>();
    Deque<BinaryTreeNode<T>> secondLevel = new LinkedList<BinaryTreeNode<T>>();
    firstLevel.push(root);
    while (!firstLevel.isEmpty()) {
        BinaryTreeNode<T> 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<Integer> bst = BinaryTreeUtil.<Integer>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}));

}

Gulfweed

Answer 18

/**
 * 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 -> 8 -> 7 -> 1 where (-> 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<String> 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<String> root) {
    ParentChain rootChain = new ParentChain(root);
    rootChain.Parent = new ParentChain(null);

    while (root != null) {

        //Going back to parent
        if(rootChain.leftVisited && 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<String> root;
    ParentChain Parent;
    boolean leftVisited = false;
    boolean rightVisited = false;

    public ParentChain(BTNode<String> node) {
        this.root = node; 
    }

    @Override
    public String toString() {
        return root.toString();
    }
}

Postmeridian

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

Answer 19

void display_without_recursion(struct btree **b) 
{
    deque< struct btree* > dtree;
        if(*b)
    dtree.push_back(*b);
        while(!dtree.empty() )
    {
        struct btree* t = dtree.front();
        cout << t->nodedata << " " ;
        dtree.pop_front();
        if(t->right)
        dtree.push_front(t->right);
        if(t->left)
        dtree.push_front(t->left);
    }
    cout << endl;
}

Brindisi

Answer 20

    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<Entry> stack = new Stack<Entry>();
        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 && 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();
        }
    }


}

Toulon

Answer 21

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->left)
        *sp++ = p;

    while (sp != stack) {
        p = sp[-1];
        if (p->right == NULL || p->right == last_visited) {
            visit(p);
            last_visited = p;
            sp--;
        } else {
            for (p = p->right; p != NULL; p = p->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.

Utility

Answer 22

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

Declinature

Answer 23

So you can use one stack to do a post order traversal.

private void PostOrderTraversal(Node pos) {
    Stack<Node> stack = new Stack<Node>();
    do {
        if (pos==null && (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());
}

Dissimulation

Answer 24

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 && root.right == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    Set<TreeNode> visited = new HashSet<>();
    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 && root.right == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    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;
    }
}

Dogbane

Answer 25

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

Sauls

Answer 26

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<Integer> postorderTraversal(TreeNode root){

 Stack<TreeNode> st=new Stack<>();
 Stack<TreeNode> st2=new Stack<>();
 ArrayList<Integer> al = new ArrayList<Integer>(); 

    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;  
}

Inn

Answer 27

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

Hetero

Answer 28

This is what I've come up for post order iterator:

    class PostOrderIterator
    implements Iterator<T> {

        private Stack<Node<T>> stack;
        private Node<T> prev;

        PostOrderIterator(Node<T> root) {
            this.stack = new Stack<>();
            recurse(root);
            this.prev = this.stack.peek();
        }

        private void recurse(Node<T> 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<T> 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<T>.

Adkison

Answer 29

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

Guadalupeguadeloupe

Answer 30

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 "stack" for the iterative variants.

One way to start is to see the recursive method and mark the locations where a call would "resume" (fresh initial call, or after a recursive call returns). Below these are marked as "RP 0", "RP 1" etc ("Resume Point"). For the case of postorder traversal:

void post(node *x)  
{  
  /* RP 0 */  
  if(x->lc) post(x->lc);  
  /* RP 1 */  
  if(x->rc) post(x->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 && (popped == curr->lc || popped == curr->rc))  
 
  while(top >= 0)  
  {  
    node *curr = stack[top];  
 
    if(!POPPED_A_CHILD())  
    {  
      /* type (x: 0) */  
      if(curr->rc || curr->lc)  
      {  
        if(curr->rc) stack[++top] = curr->rc;  
 
        if(curr->lc) stack[++top] = curr->lc;  
 
        popped = NULL;  
        continue;  
      }  
    }  
 
    /* type (x: 2) */  
    process(curr);  
    top--;  
    popped = curr;  
  }  
}

The code comments with (x: 0) and (x: 2) correspond to the "RP 0" and "RP 2" 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->lc) completes its execution. That is, we could directly shift the node to "RP 2", bypassing "RP 1". So, there is no node kept on stack at "RP 1" stage.

The POPPED_A_CHILD macro helps us deduce one of the two resume-points ("RP 0", or "RP 2").

Beora