The title of the question doesn't mention the lack of a "parent" pointer in the node. Although it isn't necessarily required for BST, many binary tree implementations do have a parent pointer.
class Node {
Node* left;
Node* right;
Node* parent;
DATA data;
};
It this is the case, imaging a diagram of the tree on paper, and draw with a pencil around the tree, going up and down, from both sides of the edges (when going down, you'll be left of the edge, and when going up, you'll be on the right side). Basically, there are 4 states:
- SouthWest: You are on the left side of the edge, going from the parent its left child
- NorthEast: Going from a left child, back to its parent
- SouthEast: Going from a parent to a right child
- NorthWest: Going from a right child, back to its parent
Traverse( Node* node )
{
enum DIRECTION {SW, NE, SE, NW};
DIRECTION direction=SW;
while( node )
{
// first, output the node data, if I'm on my way down:
if( direction==SE or direction==SW ) {
out_stream << node->data;
}
switch( direction ) {
case SW:
if( node->left ) {
// if we have a left child, keep going down left
node = node->left;
}
else if( node->right ) {
// we don't have a left child, go right
node = node->right;
DIRECTION = SE;
}
else {
// no children, go up.
DIRECTION = NE;
}
break;
case SE:
if( node->left ) {
DIRECTION = SW;
node = node->left;
}
else if( node->right ) {
node = node->right;
}
else {
DIRECTION = NW;
}
break;
case NE:
if( node->right ) {
// take a u-turn back to the right node
node = node->right;
DIRECTION = SE;
}
else {
node = node->parent;
}
break;
case NW:
node = node->parent;
break;
}
}
}
