wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> iterative binary tree traversal
        
(Message started by: nitiraj on Nov 14^th, 2008, 1:47pm)

Title: iterative binary tree traversal
Post by nitiraj on Nov 14^th, 2008, 1:47pm

I could not find if this question was asked previously so posting

Q :
O(1) space And O(n) time iterative algo. for binary tree traversal without modifying the tree( even temporarily )
i.e. we cannot use the stack which is normally done in iterative tree traversal

Question source : Introduction to algorithms ( cormen ) chap: 10 exercise : 10.4-5

I think I have the answer code in book Elis horwitz but there is no explanation. If you ppl want I will post it.

Also I think this link helps but I could not download it :
http://www.informaworld.com/smpp/content~content=a770975597~db=all

Title: Re: iterative binary tree traversal
Post by towr on Nov 14^th, 2008, 2:43pm

Unless the tree has parent links, or is threaded, or has some other feature or constraint on it, I don't see how it can be done with O(1) space without modifying the tree. So by all means post the code

Title: Re: iterative binary tree traversal
Post by nitiraj on Nov 14^th, 2008, 5:17pm

this is the code as given in book "Fundamentals of DATA STRUCTURES in C++"
by Ellis Horowitz
Sartaj Sahni
Dinesh Mehta
chapter 5
Exercises
Q 11 : Program 5.8 performs an inorder traversal without using threads,
a stack, or a parent field. Verify that the algorithm is correct by running
it on a veriety of binary trees that causes every statement to execute at least
once.

caption : Program 5.8 : O(1) space inorder traversal

code :
void Tree::NoStackInorder()
// Inorder traversal of binary tree using a fixed amount of additional storage
{
if( !root) return ; // empty binary tree

TreeNode* top = 0, *LastRight = 0, *p, *q, *r, *r1 ;
p = q = root ;
while
{
while(1)
{
if(!p->LeftChild) && (!p->RightChild)) // leaf node
{
cout << p->data ; break ;
}
if( !p->LeftChild) // visit p and move to p->RightChild
{
cout << p->data ;
r = p->RightChild;
p->RightChild = q ;
q=p;
p=r;
}
else // move to p->LeftChild
{
r = p->LeftChild;
p->LeftChild = q ;
q = p ;
p = r ;
}
} // end of inner while
// p is a leaf node, move upward to a node whose
// right subtree has not yet been examined
TreeNode*av = p ;
while( 1 )
{
if( p==root ) return ;
if( !q->LeftChild) // q is linked via RightChild
{
r = q->RightChild;
q->RightChild = p ;
p = q;
q = r;
}
else if( !q->RightChild) // q is linked via LeftChild
{
r = q->LeftChild;
q->LeftChild = p ;
p = q ;
q = r ;
cout << p->data ;
}
else // check if p is a RightChild of q
if( q == LastRight )
{
r = top;
LastRight = r->LeftChild ;
top = r->RightChild; // unstack
r->LeftChild = r->RightChild = 0 ;
r = q->RightChild ;
q->RightChild = p ;
p = q ;
q = r ;
}
else // p is LeftChild of q
{
cout << q->data ; // visit q
av->LeftChild = LastRight;
av->RightChild = top ;
top = av ;
LastRight = q ;
r = q->LeftChild;
q->LeftChild = p ; // restore link to p
r1 = q->RightChild;
q->RightChild = r ;
p = r1;
break ;
}
}// end of inner while loop
}// end of outer while loop
}

:code

By all means This code does not seem to use any stack,
or threaded tree etc.
By all means this code may not be correct. I cannot guarantee that!
In that case I am extremely sorry for this post

Other questions in the exercise
Q12 : Write a non-recursive version of function postorder using
only a fixed amount of additional space.( Use the ideas of the
previous exercise)
Q13 : Do the preceding exercise for the case of preorder.

Exact question of book : "Introduction to algorithms"
Thomas H. Cormen, Second Edition
Q10.4-5 :
Write an O(n)-time nonrecursive procedure that, given an n-node
binary tree, prints out the key of each node. Use no more than constant
extra space outside of the tree itself and do not modify the tree, even
temporarily, during the procedure.

And till this chapter the book has not discussed the threaded trees yet.

Mean while I will try to verify this algorithm.

I am sorry I tried a lots of option but this indentation thing is not working for me. So I posted it as it is

Title: Re: iterative binary tree traversal
Post by Grimbal on Nov 15^th, 2008, 2:13am

on 11/14/08 at 17:17:18, nitiraj wrote:

p->RightChild = q ;
...
p->LeftChild = q ;

It does modify the tree.

Title: Re: iterative binary tree traversal
Post by nitiraj on Nov 16^th, 2008, 10:57pm

Thanks Grimbal for pointing that out !

I was so intimidated by the question and the code that I was not able to see it.

So I learned that, to traverse a tree we use one of the following techniques
1. recursion
2. use stack
3. threaded trees
4. parent pointers( I think we need some thing more than just parent pointer. Am I right ?? )
5. modify the tree temporarily( as in this code)

But I still could not understand the algo of the code which I posted. can you please explain what it does ( just in words or simple pseudo code)

Title: Re: iterative binary tree traversal
Post by aashish.dattani on Jan 15^th, 2009, 5:49am

Hi nitiraj,

Here is an algo that does the required job without any modification. It assumes that you have a parent pointer for every node. The algo is:

InOrder_TreeTraversal()
{
prev = null;
current = root;
next = null;

while( current != null )
{
if(prev == current.parent)
{
prev = current;
next = current.left;
}

if(next == null || prev == current.left)
{
print current.value;
prev = current;
next = cuurent.right;
}

if(next == null || prev == current.right)
{
prev = current;
next = current.parent;
}

current = next;
}
}

The idea is to use another link which is a link to the parent node. So the above code do the same.

Title: Re: iterative binary tree traversal
Post by Grimbal on Jan 15^th, 2009, 6:40am

Good point.

A small simplification: update prev only at the end:
prev = current;
current = next;

update: oops, the parent pointer was mentioned by nks already.

Title: Re: iterative binary tree traversal
Post by nks on Jan 19^th, 2009, 10:03pm

Quote:

So I learned that, to traverse a tree we use one of the following techniques
1. recursion
2. use stack
3. threaded trees
4. parent pointers( I think we need some thing more than just parent pointer. Am I right ?? )
5. modify the tree temporarily( as in this code)

Like to add one more Traversal Technique is LEVEL by LEVEL - Use Queue.

Title: Re: iterative binary tree traversal
Post by cxwangyi on Dec 14^th, 2012, 5:56am

#include <iostream>

struct Node {
int key;
Node* left;
Node* right;
Node* parent;

Node(int k, Node* l, Node* r) {
key = k;
left = l;
right = r;
parent = NULL;
}
};

Node* first_kid(Node* root) {
if (root->left != NULL)
return root->left;
if (root->right != NULL)
return root->right;
return NULL;
}

Node* last_kid(Node* root) {
if (root->right != NULL)
return root->right;
if (root->left != NULL)
return root->left;
return NULL;
}

void traverse(Node* root) {
if (root == NULL) {
return; // empty tree
}

Node* prev = NULL;
Node* current = root;
Node* next = NULL;

while (current != NULL) {
if (prev == current->parent) {
std::cout << current->key << "\n";

if (current->left != NULL)
current->left->parent = current;
if (current->right != NULL)
current->right->parent = current;

prev = current;
next = first_kid(current);
if (next != NULL)
current = next;
else
current = current->parent;
}
else if (prev == first_kid(current)) {
prev = current;
next = last_kid(current);
if (next != first_kid(current))
current = next;
else
current = current->parent;
}
else if (prev == last_kid(current)) {
prev = current;
current = current->parent;
}
}
}

int main() {
Node* r = new Node(1,
NULL, // new Node(2, NULL, NULL),
new Node(3, NULL, NULL));
traverse(r);
return 0;
}

Title: Re: iterative binary tree traversal
Post by anandg on Jan 8^th, 2013, 9:43am

The algorithm used to traverse the tree inorder by making temporary modifications to the tree is called as the "Morris Algorithm". The following link describes it well :

stackoverflow.com/questions/5502916/explain-morris-inorder-tree-traversal-without-using-stacks-or-recursion

// Made link usable --towr