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

if (root.right != null)

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.

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

if(root == null)
return result.ToList();

var stack = new Stack<TreeNode>();
stack.Push(root);
while (stack.Count > 0)
{
root = stack.Pop();