Introduction

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

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

Following properties of tree node x are needed:

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

For binary trees all of these functions are quite simple; main disadvantage is necessary to remember 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.