## Tree Traversal in O(1) Space

Tree Traversal in O(1) Space by Sanjoy.

From the post:

I’ve been reading some texts recently, and came across a very interesting way to traverse a graph, called pointer reversal. The idea is this — instead of maintaining an explicit stack (of the places you’ve visited), you try to store the relevant information in the nodes themselves. One approach that works on directed graphs with two (outgoing) arcs per node is called the Deutsch-Schorr-Waite algorithm. This was later extended by Thorelli to work for directed graphs with an unknown number of (outgoing) arcs per node.

Implemented here for a tree, care to go for a more general graph?

This entry was posted
on Saturday, October 8th, 2011 at 8:14 pm and is filed under Algorithms, Graphs, Software, Trees.
You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.