There are ways to do a DFS of a tree without any sort of stack, though. This sounds more like a nitpick on stack vs set. You still have a data structure that grows in lg(n).

> There are ways to do a DFS of a tree without any sort of stack, though

What do you mean by this? You need a way to say that the unexplored nodes we've most recently found are the ones we explore first. How do you do that (with constant time operations) without what's effectively a stack?

Threaded trees was what I had in mind.[1] I believe the example there still talks of checking a visited list, though. Either a misunderstanding on my part, or on that page. I'll have to check on my books. Later, sadly. :)

[1] http://en.wikipedia.org/wiki/Threaded_binary_tree

Edit: Apologies for a quick edit. I remembered I had a short implementation on my computer. Basically, when you follow a link, you know if it was a regular link or a thread. If it was a regular link, you could still go left from the new node. Otherwise, you visit and go right. Again, keep note of whether it was a thread or not. Repeat until done. (Make sense?)

"Again, keep note of whether it was a thread or not."

This sounds like the visited list again...

You only have to remember the link you just followed. Basically, make a boolean "followedThread" and initialize to false. Then, go to the root and follow this algorithm

    if (!followedThread && left != null) 
        set followedThread <- curNode.left.isThread
        set curNode <- curNode.left.node
    else
        set followedThread <- curNode.right.isThread
        set curNode <- curNode.right.node

Only node you really have to special case is the root node, and you can do that by making its right.node == null. Then you just do this while curNode != null.

That make sense? (Also... very possible that I made a mistake here...)

Ah, great, thanks. I wasn't thinking about modifications to the tree.

Yeah, apologies if it looks like I was intentionally misleading. Was not my intent.