# 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    cousinsProgram 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  engineeringbigglesProgram 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    haargeibiggles    olgei      marty  engineering    cousinsProgram 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!	}}`

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:
`bigglesengineeringmarketingcousinsolgeihaargeichmoozymartyinternProgram 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++.