Tree Traversals: Inorder, Preorder, Postorder, Breadth-First

Dr. Lawlor, CS 202, CS, UAF

OK, so here's a simple tree code:

class treenode {
public:
	std::string data;
	treenode *left;
	treenode *right;
	treenode(std::string v,treenode *l,treenode *r) {data=v; left=l; right=r;}
};
void print(treenode *cur,int level=0)
{
	if (cur==0) { return; } // base case
	for (int indent=0;indent<level;indent++) cout<<"  ";
	cout<<cur->data<<"\n";
	print(cur->left,level+1);
	print(cur->right,level+1);
}
treenode *make_tree(void) {
	std::string x;
	if (cin>>x && x!=".") { 
		treenode *left=make_tree();
		treenode *right=make_tree();
		return new treenode(x,left,right); 
	}
	else { return NULL; }
}
int foo(void) {
	treenode *cur=make_tree();
	print(cur);
	return 0;
}

(Try this in NetRun now!)

Run with this input, using "." to represent empty tree links:

biggles
  marketing 
    chmoozy . .
    haargei intern . . .
  engineering
    olgei . marty . .
    cousins . .

I get this output:

biggles
  marketing
    chmoozy
    haargei
      intern
  engineering
    olgei
      marty
    cousins
Program complete.  Return 0 (0x0)

This is a "preorder" tree traversal. Changing the print function to print the current tree node after the children gives a "postorder" traversal:

void print(treenode *cur,int level=0)
{
	if (cur==0) { return; } // base case
	print(cur->left,level+1);
	print(cur->right,level+1);
	for (int indent=0;indent<level;indent++) cout<<"  ";
	cout<<cur->data<<"\n";
}

(Try this in NetRun now!)

And the corresponding postorder output is:

    chmoozy
      intern
    haargei
  marketing
      marty
    olgei
    cousins
  engineering
biggles
Program complete.  Return 0 (0x0)

For an "inorder" traversal, I print one child, then myself, then the other child:

void print(treenode *cur,int level=0)
{
	if (cur==0) { return; } // base case
	print(cur->left,level+1);

	for (int indent=0;indent<level;indent++) cout<<"  ";
	cout<<cur->data<<"\n";

	print(cur->right,level+1);
}

(Try this in NetRun now!)

    chmoozy
  marketing
      intern
    haargei
biggles
    olgei
      marty
  engineering
    cousins
Program complete.  Return 0 (0x0)

Note that all these functions are purely recursive.

Non-Recursive Tree Traversal

There are times when you really don't want to implement tree traversal using recursion--for example, the hardware doesn't support recursion (on a GPU, or embedded system), or recursion is using too much stack space, or you want to be able to pause the traversal and do something else for a while.

The solution is to write an iterative tree traversal, for example by keeping track of the un-visited tree nodes in a stack. Preorder is pretty easy to write:

#include <stack>
void print(treenode *cur)
{
	std::stack<treenode *> s;
	s.push(cur);
	while (s.size()>0) {
		treenode *cur=s.top(); s.pop();
		if (cur==0) continue;
		cout<<cur->data<<"\n";
		s.push(cur->right);
		s.push(cur->left); // subtle: push left last, so it'll pop first!
	}
}

(Try this in NetRun now!)

Changing this to inorder or postorder is harder than it looks--see below.

Breadth-First Tree Traversal

What if I want a level-by-level tree traversal--first the root, then both top-level children, then all the lower-level children, and so on? This is a "breadth first" traversal, unlike the "depth first" traversals like preorder, inorder, or postorder.

Well, it turns out I can get breadth first by just switching data structures to use a queue:

#include <deque>
void print(treenode *cur,int level=0)
{
	std::deque<treenode *> s;
	s.push_front(cur);
	while (s.size()>0) {
		treenode *cur=s.back(); s.pop_back();
		if (cur==0) continue;
		cout<<cur->data<<"\n";
		s.push_front(cur->right);
		s.push_front(cur->left); // subtle: push left last, so it'll pop first!
	}
}

(Try this in NetRun now!)

The breadth-first order is:

biggles
engineering
marketing
cousins
olgei
haargei
chmoozy
marty
intern
Program complete.  Return 0 (0x0)

Non-Recursive Inorder Traversal

OK, we can get rid of recursion fairly easily, and replace it with a stack to get preorder traversal, or replace it with a queue to get breadth-first traversal, but what about inorder or postorder? Well, you need to keep track of not only which nodes need to be visited, but what step we're at in the node we're currently on:

#include <stack>
class node_and_phase {
public:
	treenode *cur; // where we're at in the tree
	int phase; // which stage we're at traversing cur
	node_and_phase(treenode *c,int p) :cur(c), phase(p) {}
};
void print(treenode *root)
{
	std::stack<node_and_phase> s;
	s.push(node_and_phase(root,0));
	while (s.size()>0) {
		node_and_phase &n=s.top();
		if (n.cur==0) { s.pop(); }
		else
		switch (n.phase++) {
		case 0: s.push(node_and_phase(n.cur->left,0)); break;
		case 1: cout<<n.cur->data<<"\n"; break;
		case 2: s.push(node_and_phase(n.cur->right,0)); break;
		case 3: s.pop(); break; // <- like "return"!
		};
	}
}

(Try this in NetRun now!)

This is annoyingly tricky, but you can replace *any* recursive function with a series of manual stack manipulations and state checks. Note how the separate phases in the original inorder traversal are now just cases for a switch statement (works like a series of nested "if" blocks). This switch-on-what-to-do-next trick is one way to write coroutines in C++.