Comment by taeric

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