Introduction

Obvious traversal algorithms require O(logn) memory, i.e. an explicit or an implicit stack or a queue.

An iterative algorithm described here performs depth-first-search and requires O(1) memory. In technical terms a reference (or a pointer) to one tree node is needed. This node, called p, is a node processed in the previous step of the algorithm.

Following properties of a tree node x are needed:

• it is possible to check if a node y is a child (x.is_child(y));
• it is possible to check if a node y is a parent (y = x.parent());
• it is possible to get the first child node (x.first_child());
• it is possible to get the next sibling child node if another child y is given (x.next_sibling(y));

For binary trees all of these functions are quite simple. The main disadvantage is necessary to remember the parent of each node.

Algorithm

Initial conditions:

• p = nil
• x = root

In each iteration following cases are considered:

1. If x is a leaf, then go to the parent.
2. If p = nil, then go the first child of x,
3. If p is a parent of x, then go to the first child of x.
4. If p is a child of x, then go to next sibling node of p, but if there is no more sibling nodes, go to the parent of x.

The processing ends in 4th case, when x is root and we try to reach its parent (impossible, isn't it).

To get pre-order scheme, visiting of node have to be performed after going deeper, i.e. in cases 2, 3 and 4 (see sample code).

Download

Sample python implementation.