Tomazos Binary Tree Traverse Algorithm

Andrew Tomazos andrew@tomazos.com http://www.tomazos.com 2008-11-10

Abstract

We describe an algorithm that traverses a binary tree in O(n) time and O(1) space. Each node is visited exactly three times, once preorder, once inorder and once postorder.

Description

Imagine each node in the binary tree is a castle. Imagine that, relative to its parent, each left and right child castle is built southwestward and southeastward respectively. Now imagine each edge is a high wall connecting two castles.

We start on the ground outside of the root castle directly to its west. We start to walk south initially, and turn as necessary to always keeping the unified boundary formed by the castles and walls on our left flank. Once we reach the east side of the root castle, we will have passed by every castles westside, southside and eastside exactly once.

Each time we pass the Westside of a castle, we are visiting it preorder.

Each time we pass the Southside of a castle, we are visiting it inorder.

Each time we pass the Eastside of a castle, we are visiting it postorder.

It is possible to simulate this journey only keeping local information:

The current castle
Which of the three important sides (WEST, SOUTH, EAST) we are on of the current castle.
The current castles left and right child, if any.
The current castles parent, if any
If the current castle has a parent, whether the current castle is the left or right child of its parent.

Based on this information alone we can calculate which castle and side to visit next. We set item 1 to the root node and 2 to WEST initially, and then we loop until we have reached the EAST side of a parentless node (which must be the root).

Implementation

An implementation is provided in C:

struct node
{
    struct node* parent;
    struct node* left_child;
    struct node* right_child;
};

void visit_preorder  (struct node* p) { /* ... */ }
void visit_inorder   (struct node* p) { /* ... */ }
void visit_postorder (struct node* p) { /* ... */ }

enum side_state
{
    west,
    south,
    east
};

void tomazos_binary_tree_traverse(struct node* root)
{
    enum side_state state;
    struct node* p;

    p = root;
    state = west;

    while (p != NULL)
    {
        if (state == west)
        {
            visit_preorder(p); 
           
            if (p->left_child)
                p = p->left_child;
            else
                state = south;
        }
        
        if (state == south)
        {
            visit_inorder(p);

            if (p->right_child)
            {
                p = p->right_child;
                state = west;
            }
            else
                state = east;
        }

        if (state == east)
        {
            visit_postorder(p);

            if (p->parent)
            {
                if (p == p->parent->left_child)
                    state = south;
                else // p == p->parent->right_child
                    state = east;
            }

            p = p->parent;
        }
    }
}

Proof

In lieu of a formal proof we will sketch one: It can be shown via induction on each of the four possible child states (no children, left child, right child, both children) and each of the four possible states of the root node that the transition table will result in visiting each node exactly three times in the correct order.