Tree Traversal in O(1) Space

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.

The Deutsch-Schorr-Waite algorithm does not require adding any extra fields to the nodes. Adding fields to the node structure sort of spoils the fun — you could, for instance, have a pointer pointing to the parent of every node making stackless traversal a cup of tea. And you haven’t really saved any space! Thorelli’s approach, however, requires adding a integer to each node that can hold at least the maximum number of outgoing arcs a node can possibly have. But it can traverse graphs with more than two outgoing arcs per node. And you do save space here — if you have three outgoing arcs (maximum) per node, you could do with just a two bit integer. On x86, that’s the last two bits of a pointer.

Note that both the approaches are quite a bit more complicated than a vanilla DFS. Nevertheless, there are applications where such characteristics (of consuming only constant space) becomes important. One of the more visible ones is a GC. A GC has to traverse a (potentially) very large and complicated graph of objects, and it can’t use up too much memory (or call-stack space) when collecting — a time when memory is already a scarce resource.

I like implementing things, and while I did not implement the full algorithm proposed by Thorelli, I did implement one which traverses a tree in constant space. What more, it does not need the extra bits Thorelli’s algorithm requires.

The code is here (I believe in making code talk instead of giving long, winded descriptions): https://github.com/sanjoy/Snippets/blob/master/Traversal.cc.

The snippets repo is an idea that I recently got — I often code small things when I’m bored or want to try something out. Having a public “snippets” repo where I upload all that smelt good.

Advertisements
This entry was posted in Computers and tagged , , , , , . Bookmark the permalink.

One Response to Tree Traversal in O(1) Space

  1. beza1e1 says:

    Next, try to think with immutable data structures, such as lists in functional programming. Heureka, you reinvented finger trees! 😉

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s