Search code examples
algorithmtreetree-traversal

Is there tree traversal algorithm with fixed memory usage?

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!

Solution

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