If the nodes have parent pointers, which does tend to be somewhat common, then depth-first can be done in constant space. I haven't implemented it before, but I believe breadth-first should also take constant space in this case.