This is not a long post but it does wants to show another method to walk a tree unlike the conventional one.
I remember studying it in uni and using it i some of the exercises.
So what is the normal way to walk a tree ? using recursion or a stack (see previous post) to talk the tree Node by Node, in-order , post-order or pre order. If you use this method it Will take up to O(n) (worst case) space to walk a Binary tree B with n Nodes.
The O(n) is that big because every iteration you need to remember the parents in the branch you are on to be able to return to where you started so you could start walking the tree again in the other direction or go back up to your parent. The best case is a leveled full tree where in each level each parent got 2 siblings in this way the longest branch or the tree’s height is log2(n) and so the best case space consumption is O(log2(n)).
In case you don’t have the full tree assumtion and your tree can be partial linked list (all siblings reside on the left or right side) you need to think of a differet way to pass the tree to minimize the space the worstcase consumes.
Another way possible is walking the tree level by level – wide level walk. i’m giving here the algorithm, not in a specific programming lang though…
function walkTree(Node root):
Stack current = s1;
Stack next = s2;
while( current.isEmpty() == FALSE ):
while( current.isempty() == FALSE):
Node temp = current.pop();
if( temp.left != NIL ):
if( temp.right != NIL ):
//do something with temp.data
//end of while
So how does it work ? we are using two stack data structures but to be honest we could use queue just the same, the main thing here is to take out a node and put his siblings into the data structure for the next iteration. Each iteration we first heck if the ‘current’ data structure is empty, if it is it means we’ve finished. This is why we initialize it with the root of the tree. Then we take it out with pop() and we can d what we need with the data, then we push it’s siblings, if they exists into the ‘next’ data structure and in the en after we’ve finished processing the ‘current’ data structure we switch the ‘next’ and ‘current’ so al lthe siblings that were inserted into the ‘next’ are not the root Nodes of the new cycle.
This approach will use in the worst case O(n/2) space, we can minimize it further if we check the siblng’s siblings every iteration to O(n/4) this is the size becaue we walkt the tree’s level and the tree’s level is the biggest when we are in a full leveled tree walking the last level which is n/2 of the whole tree of n Nodes.
In the previous example’s worst case a link list would have been O(n) space here it will be O(1) space!
So when you need to walk a tree, think of the way your tree will look like and if you simple don’t know sample it, record it, profile it and then decide, that’s what interfaces are for