Author: | Wojciech Muła |
---|---|

Added on: | 17.02.2011 |

This is a solution of some exercise from Cormen handbook (AFAIR
exercise limited domain to binary trees). If you study
algorithms and data structures, please **DO NOT READ** this text.

Obvious traversal algorithms require O(log*n*) 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.

Initial conditions:

`p = nil``x = root`

In each iteration following cases are considered:

- If
`x`is a leaf, then go to the parent. - If
`p = nil`, then go the first child of`x`, - If
`p`is a parent of`x`, then go to the first child of`x`. - 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).

Sample python implementation.