The easiest way to traverse binary tree postorder iteratively. What’s the catch?

Traverse binary tree iteratively is hard to remember, especially for postorder.

Just as an illustration.

Preorder:

public IList<int> PreorderTraversal(TreeNode root)
{
    var result = new List<int>();

    var stack = new Stack<TreeNode>();

    while (stack.Count != 0 || root != null)
    {
        if (root != null)
        {
            result.Add(root.val);
            stack.Push(root);
            root = root.left;
        }
        else
        {
            root = stack.Pop();
            root = root.right;
        }
    }
    return result;
}

Inorder:

public IList<int> InorderTraversal(TreeNode root)
{
    var result = new List<int>();
    if (root == null)
        return result;

    var stack = new Stack<TreeNode>();

    while (stack.Count > 0 || root != null)
    {
        if (root != null)
        {
            stack.Push(root);
            root = root.left;
        }
        else
        {
            root = stack.Pop();
            result.Add(root.val);
            root = root.right;
        }
    }

    return result;
}

And postorder:

public IList<int> PostorderTraversal(TreeNode root)
{
    var stack = new Stack<TreeNode>();
    var result = new List<int>();
    TreeNode lastNode = null;
    TreeNode peek = null;
    while (stack.Count > 0 || root != null)
    {
        if (root != null)
        {
            stack.Push(root);
            root = root.left;
        }
        else
        {
            peek = stack.Peek();
            if(peek.right != null && lastNode != peek.right)
            {
                root = peek.right;
            }
            else
            {
                result.Add(peek.val);
                lastNode = stack.Pop();
            }
        }
    }
    return result;
}

And yeah, there are a lot of variations, but it’s still too complex to memorize.

And once I found an easy-to-remember solution:

public IList<int> PostorderTraversal(TreeNode root)
{
    var result = new List<int>();
    if(root == null)
        return result;
        
    var stack = new Stack<TreeNode>();
    stack.Push(root);
    while (stack.Count > 0)
    {
        root = stack.Pop();
        
        result.Insert(0, root.val);
            
        if (root.left != null)
            stack.Push(root.left);
        
        if (root.right != null)
            stack.Push(root.right);
    }
    return result;
}

It looks concise and similar to the recursive approach:

public IList<int> InorderTraversal(TreeNode root)
{
    var result = new List<int>();

    if (root == null)
        return result;

    if (root.left != null)
        result.AddRange(InorderTraversal(root.left));
        
    result.Add(root.val);
    
    if (root.right != null)
        result.AddRange(InorderTraversal(root.right));

    return result;
}

I wish it was so lucky. But look at this line:

result.Insert(0, root.val);

Inserting to the List costs O(N) both in C# and Java. So, when we put such code within the loop we will get O(N²) as total complexity.

That’s really bad.

And I noticed again that nobody thinks in terms of time complexity.

Okay, there was one comment there (“adding the values in the list looks O(n²) and might not scale well for large data…”) and recommendation to use linked list instead of list.

Something like:

public IList<int> PostorderTraversal(TreeNode root)
{
    var result = new LinkedList<int>();
    
    if(root == null)
        return result.ToList();
        
    var stack = new Stack<TreeNode>();
    stack.Push(root);
    while (stack.Count > 0)
    {
        root = stack.Pop();
        
        result.AddFirst(root.val);
            
        if (root.left != null)
            stack.Push(root.left);
        
        if (root.right != null)
            stack.Push(root.right);
    }
    return result.ToList();
}

And this more interesting. Although you need an additional pass to convert result to list, it gives O(N) as time complexity with the same space complexity.

But, yeah, it’s still not the canonical solution with one stack only.