Traversing tree without stack

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(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:

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


Initial conditions:

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).


Sample python implementation.