Iterative Tree Traversal

2010/11/16

While studying for an interview, I some how got it into my head that I should understand the iterative algorithms for the three standard tree traversal methods (pre-, post-, in-). While the recursive algorithms for these are straightforward and intuitive, the iterative ones are most certainly not. Worse, googling on this topic turned up a lot of incomplete or just plain wrong solutions.

With some painstaking work I believe I came up with some nearly as simple as possible solutions. Some solutions I found required parent pointers, some required visit markers. These require neither of these.

After each algorithm, I include a walkthrough of the algorithm based on this sample tree from the Wikipedia tree traversal page.

Pre-order,

void preOrderIterative(Node n) {
	Stack<Node> s = new new Stack<Node>();
	s.push(n);

	while (!s.empty()) {
		n = s.pop();
		n.visit();

		if (n.right != null) {
			s.push(n.right);
		}
		if (n.left != null) {
			s.push(n.left);
		}
	}
}

Each line of the example shows the stack at the beginning of the iteration, the set of visited nodes so far after the iteration, and the stack at the end of the iteration.

1: s={}, visited={F}, s={B,G}
2: s={G}, visited={F,B}, s={A,D,G}
3: s={D,G}, visited={F,B,A}, s={D,G}
4: s={G}, visited={F,B,A,D}, s={C,E,G}
5: s={E,G}, visited={F,B,A,D,C}, s={E,G}
6: s={G}, visited={F,B,A,D,C,E}, s={G}
7: s={}, visited={F,B,A,D,C,E,G}, s={I}
8: s={}, visited={F,B,A,D,C,E,G,I}, s={H}
9: s={}, visited={F,B,A,D,C,E,G,I,H}, s={}

Post-order,

This one uses two stacks. It consumes the input stack and builds the output stack. At the end of the method, it pops each node from the output stack and visits it.

void postOrderIterative(Node n) {
	Stack<Node> s = new new Stack<Node>();
	Stack<Node> o = new new Stack<Node>();
	s.push(n);

	while (!s.empty()) {
		n = s.pop();
		o.push(n);

		if (n.left != null) {
			s.push(n.left);
		if (n.right != null) {
			s.push(n.right);
		}
	}
	while (!o.empty()) {
		o.pop().visit();
	}
}

Each line of the example below shows state of the input stack and output stack after the iteration.

1: out={F}, in={G,B}
2: out={G,F}, in={I,B}
3: out={I,G,F}, in={H,B}
4: out={H,I,G,F}, in={B}
5: out={B,H,I,G,F}, in={D,A}
6: out={D,B,H,I,G,F}, in={E,C,A}
7: out={E,D,B,H,I,G,F}, in={C,A}
8: out={C,E,D,B,H,I,G,F}, in={A}
9: out={A,C,E,D,B,H,I,G,F}, in={}

In-order,

void inOrderIterative(Node n) {
	Stack<Node> s = new new Stack<Node>();
	s.push(n);

	while (!s.empty()) {
		while (n.left != null) {
			n = n.left;
			s.push(n);
		}
		n = s.pop();
		n.visit();
		if (n.right != null) {
			s.push(n.right);
		}
	}
}

Each line of the example shows the stack at the beginning of the iteration, the set of visited nodes so far after the iteration, and the stack at the end of the iteration.

1: s={A,B,F}, v={A}, s={B,F}
2: s={B,F}, v={A,B}, s={D,F}
3: s={C,D,F}, v={A,B,C}, s={D,F}
4: s={D,F}, v={A,B,C,D}, s={E,F}
5: s={E,F}, v={A,B,C,D,E}, s={F}
6: s={F}, v={A,B,C,D,E,F}, s={G}
7: s={G}, v={A,B,C,D,E,F,G}, s={I}
8: s={H,I}, v={A,B,C,D,E,F,G,H}, s={I}
9: s={I}, v={A,B,C,D,E,F,G,H,I}, s={}
Advertisements