# 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.

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!)

`bigglesengineeringmarketingcousinsolgeihaargeichmoozymartyinternProgram complete.  Return 0 (0x0)`
`#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"!		};	}}`