Iterative Tree Traversal

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

7 Responses to Iterative Tree Traversal

  1. Simone says:

    Hi Jeffrey,well done! I was trying to find similar algorithms and I luckily got on your website. I am studying for an exam and I really needed some help, so thank you!
    Just a quick question (I hope you could answer me), in the last algorithm (in-order), in line 06 (while (n.left != null)), I suppose that we are missing a further control? I mean, if n hasn’t elements on its right, n stays the same and (if the previous Ns didn’t have right elements as well) we end up doing the second while (line 06, again) for another time. I guess this issue is present only when elements do not have children in the right. (for example 3 linked elements without children on the right).
    Do you agree? or…maybe it’s just too late here…

    Let me know, any help will be really appreciated!
    Thank you
    Simone

  2. karthi says:

    In the preorder algo, the output for input : 10 4 2 7 12 11 14 13
    is 10 4 2 7 12 11 14 13

    but its givin 10 12 14 13 11 4 7 2

    private static void IterativePreOrderTraversal(node root)
    {
    if(root == null) return;
    Stack s = new Stack();

    s.Push(root);

    while (s.Count!=0)
    {
    node cur = s.Pop();
    Console.Write(” right before current left i guess..

    please correct me if i ‘m wrong

  3. Hridoyjit says:

    thank you very much for the non recursive algorithm of the post order tree traversal. Impressive and very much helpful… 🙂 🙂

  4. Stone says:

    The inorder code is wrong! Unfortunately Google doesn’t know that and rank this blog post high.

    • KK says:

      Yes. Inorder code is wrong. In the if block checking whether right node is null or not, the node needs to be updated.

      n = n.right;

      I think this should work.

      • Dhiraj says:

        I think the problem goes beyond that. Even if we were to make this right node update, there’s still a problem with the left nodes traversal.
        Since we do not keep track of visited nodes explicitly, the left child traversal block will keep traversing the same next child over and over again.

    • Dhiraj says:

      Stone, you are right. The inorder Traversal could be stuck in an infinite loop in some cases, printing the leftmost node and and its parent one after the other forever.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: