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抯 without checking the condition for that branch, much the way C抯 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抰 actually use a switch statement in C for this because the case conditions in this algorithm wouldn抰 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.)