Is there tree traversal algorithm with fixed memory usage?

Question

I have first node of the tree. Something like that:

class TreeNode {
   int uniqueValue;
   List<TreeNode> children;
}

I want to find the most memory efficient way to print all nodes of the tree. Tree may be big or VERY BIG. It can be deep or wide. I know algorithms with recursion and with stack. What I want to find is algorithm that use fixed amount memory independently from graph size.

Tree is NOT binary!

Answer 1

There is no such O(1) algorithm. Memory usage in the worst case is always O(N). You can "cheat" by adding fields to support traversal directly onto the graph node. This way if you are able to load the graph to memory you can traverse it (with either BFS or DFS).

Answer 2

If the tree happens to be stored in a flat heap-like stream, such as a long parenthesized list, traversing it only takes enough memory to record your position in the stream, which takes O(log(N)) bits.

Of course, as Lior says, you could just depth-first walk it using a stack in O(log(N)) bits.

If your tree referenced every particle in the universe (1e85, say), technically you'd only need, let's see - 85 times 3.3 = 281 bits = about 35 bytes. I assume you can handle that.