While studying traversal algorithms, I was stumped by writing the iterative versions of in-order and post-order traversals. This is my attempts at organizing my thoughts on why it is deceptively simple and how I might be able to change my thinking to approach similar problems.

Below are the recursive and iterative versions of in-order traversal written in JavaScript.

var inOrderArr = [];
var inOrderRecursive = function(node) {
	if (node.left != null) {
		inOrderRecursive(node.left);
	}
	inOrderArr.push(node);
	if (node.right != null) {
		inOrderRecursive(node.right);
	}
};

var inOrder = function(node) {
	var curr = null,
		stack = [],
		visit = [];
	
	curr = node;
	while (stack.length > 0 || curr != null) {
		if (curr != null) {
			stack.push(curr);
			curr = curr.left;
		}
		else {
			curr = stack.pop();
			visit.push(curr);
			curr = curr.right;
		}
	}
	
	return visit;
};

Thinking about converting a recursive algorithm to an iterative one should not to be too difficult, right? After all, a recursive algorithm uses the system stack to keep track of where it is, therefore the iterative algorithm should also incorporate a stack. But the way the stack is used can be deceptive. Unless you get a little creative.

The recursive in-order traversal algorithm is short and sweet, essentially 3 lines long: visit the left node (recursively), push the current node onto the visited array, then visit the right node (recursively). What’s occurring in the background is a little more complicated.

The first call (A) chugs along until it notices a recursive call to itself, so it puts its current state (A) on a stack then recursively calls itself passing in the left child node. It (B) chugs along, hits the same point as before, puts its current state (B) on a stack, and recursively calls itself with the left child node. And so on, until the left child node is null. Then, it adds the current node to the visited array, and then visits its right child node.

The sequence repeats itself with the right child’s node – chugs along, finds a recursive call, puts its current state (N) on the stack, explores its left children, then its right, adding to the stack each time a recursive call is made. Then it (some call X) finishes everything in the method and returns. It (X) pops off the stack. At this point, the newly exposed node (X – 1) has finished exploring its left branch, so it gets added to the visited array, then repeats the entire process on its right branch. It finishes everything in the method and returns, pops off the stack, exposing a new node (X – 2) that has already finished exploring its left branch. And so on back up the stack.

The difficulty with translating this into an iterative algorithm is aside from setting flags, there is no clean way to say “the left child has been visited” using if-else statements. It’s easy to visit leaf nodes by checking if the children are null, but the nodes in between will never get put in the visited array. What is more likely is I get caught in an infinite loop.

The creative/sneaky way around this is to put onto the stack nodes I have already seen. Meaning, the stack will initially be empty, my current node will not be null. Since it is not null, it gets put onto the stack and I traverse left. I repeat, this time my current node is the left child. If my left child happens to be null, then I will pop off of the stack, add the popped element to the visited array, then attempt to traverse right. The loop repeats, first attempting to go left if my node is not null, otherwise the stack is popped and pushed onto the visited array, then I attempt to go right.

The very subtle difference is I don’t check if the children are null (as with the recursive version), but if the current node itself is null. In the iterative version, I traverse regardless if I end up on null, because that tells me I need to pop the stack. This particular state of the node being null occurs irregardless if I went left or right. Trying to determine when to pop using if-else statements and checking children was difficult, messy, and I have a suspicion, impossible.

Disclaimer: Code may not be perfect, there may be incorrect statements, etc. The point is to put in English roughly what is occurring and translating abstract concepts into words so that I have a tool in my toolbox if I run into the more general case of needing to write an iterative algorithm based off of a recursive algorithm that requires both head and tail recursion.