Binary tree postorder traversal without recursion

We have seen postorder traversal algorithm for a binary tree, but it was a recursive version. In this article, we'll take a look at the iterative implementation.

The postorder binary tree traversal algorithm can be described:

• Visit the left subtree
• Visit the right subtree
• Visit the root

A tree node is represented like this:

    public class TreeNode
    {
        public int Value;
        public TreeNode Left;
        public TreeNode Right;
    
        public TreeNode(int value)
        {
            Value = value;
        }
    }

 

 

During postorder traversal, nodes will be printed in the following order: 5, 7, 4, 8, 3, 2. The most interesting part is the opposite order (from the end to start). Let's see on the simple example of how we can make the postorder traversal.

 

 

The nodes will be printed in the following order: 5, 7, 4. This traversal can be created for instance, if visit nodes in order:

• Visit the root
• Visit the right subtree
• Visit the left subtree

and put values into another result stack, like this:

 

Algorithm

• Create two stacks
  • result stack
  • stack for the traversal
• While stack is not empty
  • pop a node from the stack and push into result stack
  • push left child to the stack (if exists)
  • push right child to the stack (if exists)
• Print traversal

Code

    public void PostorderTraversal(TreeNode root)
    {
        if (root == null)
        {
            return;
        }

        var result = new Stack<int>();
        var stack = new Stack<TreeNode>();

        stack.Push(root);

        while (stack.Count != 0)
        {
            TreeNode node = stack.Pop();
            result.Push(node.Value);

            if (node.Left != null)
            {
                stack.Push(node.Left);
            }

            if (node.Right != null)
            {
                stack.Push(node.Right);
            }
        }

        while (result.Count != 0)
        {
            // print value
            Console.WriteLine(result.Pop());
        }
    }

Time Complexity: O(n)