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…
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | function walkTree(Node root): Stack s1,s2; Stack current = s1; Stack next = s2; current.push(root); while( current.isEmpty() == FALSE ): while( current.isempty() == FALSE): Node temp = current.pop(); if( temp.left != NIL ): next.push(temp.left); if( temp.right != NIL ): next.push(temp.right); //do something with temp.data //end of while swap(current, next); |
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 
I checked out something comparable to your post via google news… I became intrigued and began looking around, and landed here… in any case, I believe that I somewhat agree with what you talk about here. However I am going to go see what else I can find too.
grando a ricogo si codetimes folôncia con amensa. vevetões anudiza se arelo son cadiar mi rasso deiro y ataco antes prorcevo.
I am not sure where you’re getting your information, but great topic. I needs to spend some time learning much more or understanding more. Thanks for excellent info I was looking for this info for my mission.
Significant document , I am hoping your commentary usually are not fake :*)
Really good blog you’ve got here. You will see me reading through your stuff often. Saved as a favorite!
10x
excellent post. many thanks for sharing this resource. thanks so much for everything you’ve put into it this blog has me coming back time and time again.