In my previous post I was talking about drawbacks of recursive approach when traversing tree structures.
In comments on that post, Daemin and w-g mentioned then tail-recursion can be used to avoid function call overhead. Tail-recursion really helps if:
a) language of use supports it
b) your algorithm makes it possible to make a recursive call the last operation in the function
Since, tail-recursion approach is still a recursive one and there is no guarantee that the language of use will support it or the algorithm will allow it - best way not to go into trouble is to make no recursive calls at all.
Here, I'll present non-recursive binary tree traversal. Binary tree is not balanced. To make non-recursive approach possible - tree node was extended with special meta information. It includes reference to the node's parent and a special flag. Flag indicates if node was previously visited during traversal process.
Binary tree node definition in code
class TreeNode {public int Value; public TreeNode Left; public TreeNode Right; public TreeNode Parent; public byte Visited; public TreeNode(int value) {Value = value; } } |
Next comes recursive iterator. This method demonstrates recursive approach. It is self-explanatory and very easy to implement. All job is done via recursive call to RecursiveIterator method.
private void RecursiveIterator(TreeNode node) {Console.Write(node.Value + " "); if (node.Left != null) RecursiveIterator(node.Left); if (node.Right != null) RecursiveIterator(node.Right); } |
Non-recursive approach on the other hand uses iteration and additional variables to do tree traversal.
private void NonRecursive() { TreeNode currNode = root;while (true) {if (currNode == null) break;if (currNode.Left != null && currNode.Left.Visited != 1) currNode = currNode.Left; else if (currNode.Right != null && currNode.Right.Visited != 1) currNode = currNode.Right; else if (currNode.Visited == 0) {Console.Write(currNode.Value + " "); currNode.Visited = 1; } currNode = currNode.Parent; } } |
Iterative approach is more complicated then recursive, it uses additional data (Parent reference and Visited flag).
So, generally, when you know that your tree structures won't be very deep recursive approach will do. And in the case, when tree depth is quite big, it is better to consider iterative approach.
Posts
Hi, I was looking at your algorithm and I think there should be an "else" before the final "currNode = currNode.parent;" line. Otherwise, it will infinitely bounce between the root and the left child node, and not accomplish anything.
ReplyDeleteOther than that, thanks for posting this. It helped me clarify the iterative approach in my head.
Thanks for pointing this out.
ReplyDeleteI'll make the correction.
I saw your code, and here is another possible version for non recursive tree traversal:
ReplyDeletepublic void printInOrderNR(){
BinaryTreeNode node = root;
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
while (true){
if (node != null){
stack.push(node);
node = node.getLeft();
}else{
if (stack.empty())
return;
node = stack.pop();
System.out.println(node.getData());
node = node.getRight();
}
}
}
The advantage is that the tree node definition does not need extra information. Maybe the draw back is the use of the stack.
Yes, stack based approach also looks good.
ReplyDeleteThere is one drawback here. Imagine what happens if you'dd have to parse the tree twice - you'dd have to use another visited flag, since the first one is used up ;)
ReplyDelete"There is one drawback here. Imagine what happens if you'dd have to parse the tree twice - you'dd have to use another visited flag, since the first one is used up ;)"
ReplyDeleteOr you can just reset the flags after each complete call.
I thing your recursive solution is meant for pre-order traversal and your iterative solution is for post-order traversal. This was a bit confusing. You should have name your functions accordingly, not like RecursiveIterator.
ReplyDeleteFYI, you can do this without a "visited" flag and without a stack. It just requires the use of two pointers (you do need parent pointers in the tree nodes though--although you can dispense with those if you use something like the Schorr-Waite algorithm[1]).
ReplyDeleteThe idea is you keep a "curr" and "prev" pointer and use the relationship between the two to tell you where you are in the traversal. If prev is above curr, then you're going down. If prev is below curr to the left, then you're going up and need to visit the right subtree. If prev is below curr to the right, then you have already visited all nodes below curr and can move up to its parent. It's a fun exercise to work out the details.
[1] H. Schorr, W. M. Waite. "An efficient machine-independent procedure for garbage collection in various list structures." Communications of the ACM, 1967.
Thanks, Stephen
ReplyDeleteI'll look at it.
If I may praise the original code at the expense of the proposed changes (using stack<> or pointers), the former is more portable and arguably easier to read. Besides, using stack seems like a bit of a cheat if our goal is to be nonrecursive. Frankly, I think it's a shame our technology relies so heavily on recursive data structures like XML for transfer--there have to be algorithms on both ends to pack and unpack them. For me, the test of a good algoirthm for parsing data is whether it can be autogenerated by precompilation or runtime code generators (depending on langauge or implementation strategy), since programmers should not have to roll out custom algorithms to handle data so long as that data itself fits a canonical model. Of the solutions listed here, I think the original fits that criterion best.
ReplyDeleteHey
ReplyDeletecan anyone please help writting code for "Non-recursive All purpose Binary Tree traversals" in JAVA
Hi
ReplyDeleteA great code, but how to reset the 'Visited' flag. Because once I call the nonrecursive traversal function, I won't be able to call it again without resetting the flag. Please reply ASAP.
Ideally, to perform numerous iterations on the same tree you should implement special iterator class that will store information about visited nodes.
ReplyDeleteIn the original code tree node had information .Visited prop. The iterator class can have table (Dictionary) where there will be information if the node was already visited.
I have to disagree about using a Dictionary. If I understand how you want to use it, there would be a dictionary of nodes associated with each iterator. That will use O(n) space per iterator even when the tree is perfectly balanced, while a recursive solution, or a solution with an explicit stack would both be O(log n) space. All that extra allocation will impact performance.
ReplyDeleteYou can support multiple (sequential) visits with the flag approach. Just flip it from 0 to 1 the first time and from 1 to 0 the second time (you can tell which you need by looking at the flag field of the root before you traverse).
If you need multiple iterators going at the same time, use the approach with a prev and curr pointer. In fact, I see no reason not to always use that approach if you have parent pointers sitting around. With the two-pointer approach, you don't have to alter the global state, which is good for cache performance and fits nicely into the iterator model.
If there are multiple iterators - flag approach can work only if iterators are iterating through the tree sequantialy that is one by one.
ReplyDeleteDo curr and prev pointer approach support non recursive iteration?
Here is the two pointer solution (in C).
ReplyDeletetypedef struct tree {
struct tree *parent;
struct tree *left;
struct tree *right;
int data;
} Tree;
typedef Tree *Treep;
void traverse(Treep t) {
Treep prev = 0;
while (t != 0) {
while (t != 0) {
if (prev == t->parent) {
// moving down, try left first, then right
prev = t;
if (t->left != 0)
t = t->left;
else
t = t->right;
}
else if (prev == t->left) {
// just moved up a left branch, traverse the right.
prev = t;
t = t->right;
}
else if (prev == t->right) {
// just moved up a right branch, keep going
prev = t;
t = t->parent;
}
}
if (prev != 0) // hit a 0 on the right, jump over prev.
t = prev->parent;
}
}
This can be done with just one loop and one temp pointer if you use the knowledge that you are using a left first or right first traversal. When you have to decide to go up, check if your temp is left of your parent or right of your parent. So assume u were doing left processing first, then if temp is left of parent, go to right of parent and continue to process left first. When you are right of your parent, start a while loop and continue to climb until you are not right of your parent or parent nul. In this loop keep updating parent and temp. Should be fast and doesn't change tree.
DeleteI found that the two-pointer method was actually slower for my kd-tree class in Python than straight recursion. Maybe I was just doing it wrong. The queue worked very well, but was only a little faster than recursion. These trees aren't very deep, though: even a tree with 100,000 elements only has a depth of 17 levels.
ReplyDeleteYeah, I wouldn't expect the two-pointer version to be faster. Its main advantage is space-efficiency when you already have parent pointers in the tree. But as you pointed out, we're talking about a logarithmic amount of space, so its not going to matter for most applications.
ReplyDeleteSimilar to that by stephen, just use one while loop instead of two nested loops.
ReplyDeletetypedef struct tree {
struct tree *parent;
struct tree *left;
struct tree *right;
int data;
} Tree;
void traverse(Tree* root){
//assert(root.parent==0);
Tree* prev=root->parent;
Tree* curr=root;
while(curr){
if(prev==curr->parent)
if(curr->left) {
prev=curr;
curr=curr->left;
continue;
}else prev=curr->left;
if(prev==curr->left)
if(curr->right) {
prev=curr;
curr=curr->right;
continue;
}else prev=curr->right;
if(prev==curr->right){
prev=curr;
curr=curr->parent;
} //^allow curr=0 to quit
} //end of while.
return;
}
i dont know if this works in C but if you implement the above it does not work because the parent variable of the knodes is not being modified so you need to add
ReplyDeletewhile(curr){
if(prev==curr->parent)
if(curr->left) {
prev=curr;
curr=curr->left;
curr->parent = prev;
continue;
}else prev=curr->left;
if(prev==curr->left)
if(curr->right) {
prev=curr;
curr=curr->right;
curr->parent = prev;
continue;
}else prev=curr->right;
I had assumed the tree was already set up with parent pointers pointing to the correct nodes. The appropriate parent pointer values only depend on the structure of the tree, so the best place to set them is when changing the structure (adding nodes, deleting nodes, rebalancing, etc.)
ReplyDeleteYou have to express more your opinion to attract more readers, because just a video or plain text without any personal approach is not that valuable. But it is just form my point of view
ReplyDeleteIs there any solution possible without the parent node and not using a stack?
ReplyDeleteThere is the Schorr-Waite traversal algorithm[1], commonly used for garbage collection. It tracks state by rotating pointers. The algorithm works for arbitrary graphs if you add two bits of extra state per node. If there are no cycles, there is a variant due to Lindstrom[2] that requires no extra space.
ReplyDelete[1] H. Schorr and W. Waite. An efficient machine independent procedure for garbage collection in various list structures. Communications of the ACM, 10(8):501–506, August 1967.
[2] G. Lindstrom. Scanning list structures without stacks or tag bits. Information Processing Letters, 2(2):47–51, June 1973.
This is my stack approach that doesn't involve a Parent Node. Stacks are simple enough, so I hope this is able to help someone... The methods are rather self-explanatory from their names.
ReplyDeletepublic void iterativeinorder(Node localroot)
{
Node current = localroot;
Stack stack = new Stack();
while (true)
{
if (current == null)
break;
else
{
if (current.leftchild != null &&
current.leftchild.getvisitflag() != true)
{
stack.push(current);
current = current.leftchild;
}//end if
else
{
if (current.getvisitflag() != true)
{
current.displaynode();
current.setvisitflag();
}//end if
else
{
if (current.rightchild != null &&
current.rightchild.getvisitflag() != true)
{
stack.push(current);
current = current.rightchild;
}//end if
else
{
if (stack.isempty())
break;
current = stack.pop();
}//end else concerning right child
}//end else (current.getvisitflag() == true)
}//end else concerning left child
}//end else (current != null)
}//end while
resetflags(localroot);
}//end iterativeinorder
Sorry for the rather awful formatting, lol. It looks a bit better in an IDE.
I think it's a shame our technology relies so heavily on recursive data structures like XML for transfer--there have to be algorithms on both ends to pack and unpack them.
ReplyDeleteRuby On Rails Developers
in case we have to implement the same thing for a non binary tree...would this code be able to work the same way? i guess the problem for a non binary tree would be there is no restriction on the no of children a node might have, so we can't just have only 2 pointers, we would neeed to have multiple pointers. any suggestions on how the above code can be modified to achieve this?
ReplyDelete