Tree traversal without recursion: the tree as a state machine

I am currently working my way through Higher-Order Perl, and as you’d expect, the subject of tree traversal makes a frequent apperance:

First, as an introductory example to recursion;
then, when discussing how to turn recursive functions into iterators using an explicit stack (which permits breadth-first searching);
again recursively, in the section on tail call elimination, where the tail-recursive call is eliminated first, and the other recursive call is then replaced by an explicit stack.

There may be even more appearances later in the book that I’ve yet to discover; as I said, I’m not through with it yet. However, the book changes topic after that, at least momentarily, so I stopped to ponder. It occured to me that this is the entire extent to which discussions of tree traversal typically go. Another obvious option that occured to me many years ago is not discussed anywhere that I’ve seen, though it is occasionally mentioned as a possibility in passing:

You can get rid of any stacks whatsoever by keeping a parent pointer in the tree node data structure. Effectively, this turns the tree into a (sort of) state machine. While traversing, you need no memory other than the current and the previous node/state. The traversal algorithm is very simple:

If the previous node is this node’s parent node, descend to the left child node.
If the previous node is this node’s left child node, descend to the right child node.
If the previous node is this node’s right child node, ascend to the parent node.

Obviously, if there is no left child to descend to, you try the right one; and if there is no right child to descend to, you ascend to the parent. Traversal is complete when an attempt to ascend to the parent node fails because there is no parent. Pre-, post- and in-order traversal can be implemented simply by changing which of the conditions implies that the current node must be visited: if you visit the node when coming from…

… the parent node, you get pre-order traversal.
… the left child node; you get in-order traversal.
… the right child node; you get post-order traversal.

Assuming all tree nodes are instances of a class which has parent, left and right methods and uses undef to signify the absence of a pointer, the following is an implementation of the in-order version of the traversal algorithm in Perl:

sub traverse_tree {
    my ( $tree_root, $visitor_callback ) = @_;
    my ( $curr_node, $prev_node ) = $tree_root;

    while( $curr_node ) {
        my $next_node;

        if( $prev_node == $curr_node->parent ) {
            $next_node = $curr_node->left;
            if( not $next_node ) {
                $visitor_callback->( $curr_node );
                $next_node = $curr_node->right || $curr_node->parent;
            }
        }
        elsif( $prev_node == $curr_node->left ) {
            $visitor_callback->( $curr_node );
            $next_node = $curr_node->right || $curr_node->parent;
        }
        elsif( $prev_node == $curr_node->right ) {
            $next_node = $curr_node->parent;
        }

        ( $prev_node, $curr_node ) = ( $curr_node, $next_node );
    }
}
[download]

This is the most straightforward implementation, which does have a fault: there is some code duplication between the coming-from-parent and coming-from-left-child states. The complication comes about because node visiting must be ensured even when the node does not have the particular pointer to come from; eg. in the case of in-order traversal, you visit the current node when you come from the left child node; but when a node has no left child node, you must still ensure that the node will be visited. The discovery that the left child node is absent will happen when the previous node was the parent, and so that state must ensure to visit the current node before going on to try to descend to the right.

The fix is conceptually simple, but not easy to express in code. You need a way to fall through from the body of one branch to another’s without checking the condition for that branch, much the way C’s switch statement works, where branches fall through by default and require an explicit break to exit. A switch statement in C is simply a structured expression of a jump table (but note that you couldn’t actually use a switch statement in C for this because the case conditions in this algorithm wouldn’t be constant expressions); so the Perl version will need a couple of explicit gotos:

sub traverse_tree {
    my ( $tree_root, $visitor_callback ) = @_;
    my ( $curr_node, $prev_node ) = $tree_root;

    while( $curr_node ) {
        my $next_node;

        {
            goto FROM_PARENT if $prev_node == $curr_node->parent;
            goto FROM_LEFT   if $prev_node == $curr_node->left;
            goto FROM_RIGHT  if $prev_node == $curr_node->right;

            FROM_PARENT:
                last if $next_node = $curr_node->left;

            FROM_LEFT:
                $visitor_callback->( $curr_node );
                last if $next_node = $curr_node->right;

            FROM_RIGHT:
                $next_node = $curr_node->parent;
        }

        ( $prev_node, $curr_node ) = ( $curr_node, $next_node );
    }
}
[download]

In this rendition of the algorithm, the reformulation required to implement pre- or post-order traversal is trivial: you just move the callback invocation to the appropriate label.

(It is in fact quite simple to implement all three variants in a single function: just put a call in every branch and make them conditional on an extra parameter, eg. $visitor_callback->( $curr_node ) if $order == -1; where $order == 0 means in-order traversal and in that case the parameter is optional.)

Makeshifts last the longest.

Comment on Tree traversal without recursion: the tree as a state machine Select or Download Code

Replies are listed 'Best First'.
Re: Tree traversal without recursion: the tree as a state machine by dragonchild (Archbishop) on Feb 16, 2007 at 17:21 UTC
Tree implements an iterative callback for pre-order, post-order, and level-order traversals. If you call traverse() in scalar context, you'll be given a callback which will return the next node when invoked. My criteria for good software: Does it work? Can someone else come in, make a change, and be reasonably certain no bugs were introduced?	[reply]
Re: Tree traversal without recursion: the tree as a state machine by pKai (Priest) on Feb 16, 2007 at 22:54 UTC
It's no coincidence that stacks have a close relationship with trees. You can get rid of any stacks whatsoever by keeping a parent pointer in the tree node data structure. I wouldn't say you "get rid of any stacks" here. While you don't implement the stack as a list in classical ways, the list of "parent pointer(s)" between the root and the current node at any given moment of the traversal forms a stack. While traversing, you need no memory other than the current and the previous node/state. "previous node/state" obviously refers to the "top of stack", the single point where a stack is accessible.	[reply]
Re^2: Tree traversal without recursion: the tree as a state machine by Aristotle (Chancellor) on Feb 16, 2007 at 23:41 UTC
Yes, it’s just a different form of storage of the same data. Obviously, you have to store enough information to find your way around the tree somewhere. If it’s not one place, it’s another. However, this algorithm really does not use a stack, at least not if you define a stack in the only way which makes sense – that is, as a data structure whose defining property is support for the operations of pushing things onto the top and popping them off the top. It consumes more space, of course, to keep all those parent pointers around. If you use a stack, they are transient and you only need O(log n) stack space, whereas it’s O(n) if you store the pointers with the nodes – another way in which the two approaches are truly distinct. What I like about this approach (which is what compelled me to post it) is the exceptional simplicity of the traversal algorithm. When it first occured to me, it seemed too simple to work – but no, the position and direction of the traverser encodes enough information to guide its path along the entire tree in the right order without any ambiguity. Makeshifts last the longest.	[reply]


Perl Monk, Perl Meditation
	PerlMonks