Tree traversal: Difference between revisions

Revision as of 23:37, 12 March 2005

Revision as of 23:41, 12 March 2005

Line 60:

== Iterative traversal ==

All of the above recursive algorithms use stack space proportional to the depth of the tree. If we store on each node a reference to its parent, then we can implement all of these traversals using[[in-place only constant spacealgorithm|in-place]] using a simple iterative algorithm. The parent references occupy much more space, however; this is only really useful if the parent references are needed anyway, or stack space in particular is limited. For example, here is an iterative algorithm for in-order traversal:

<pre>