wu :: forums
« wu :: forums - iterative binary tree traversal »

Welcome, Guest. Please Login or Register.
Jul 23rd, 2014, 6:57am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: Eigenray, william wu, Grimbal, SMQ, Icarus, towr, ThudnBlunder)
   iterative binary tree traversal
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: iterative binary tree traversal  (Read 7061 times)
nitiraj
Newbie
*





   


Posts: 11
iterative binary tree traversal  
« on: Nov 14th, 2008, 1:47pm »
Quote Quote Modify Modify

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
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13090
Re: iterative binary tree traversal  
« Reply #1 on: Nov 14th, 2008, 2:43pm »
Quote Quote Modify Modify

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
« Last Edit: Nov 14th, 2008, 2:46pm by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
nitiraj
Newbie
*





   


Posts: 11
Re: iterative binary tree traversal  
« Reply #2 on: Nov 14th, 2008, 5:17pm »
Quote Quote Modify Modify

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
« Last Edit: Nov 14th, 2008, 5:25pm by nitiraj » IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7009
Re: iterative binary tree traversal  
« Reply #3 on: Nov 15th, 2008, 2:13am »
Quote Quote Modify Modify

on Nov 14th, 2008, 5:17pm, nitiraj wrote:
p->RightChild = q ;
...
p->LeftChild = q ;

It does modify the tree.
« Last Edit: Nov 15th, 2008, 2:13am by Grimbal » IP Logged
nitiraj
Newbie
*





   


Posts: 11
Re: iterative binary tree traversal  
« Reply #4 on: Nov 16th, 2008, 10:57pm »
Quote Quote Modify Modify

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)
IP Logged
aashish.dattani
Newbie
*





   


Posts: 1
Re: iterative binary tree traversal  
« Reply #5 on: Jan 15th, 2009, 5:49am »
Quote Quote Modify Modify

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.
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7009
Re: iterative binary tree traversal  
« Reply #6 on: Jan 15th, 2009, 6:40am »
Quote Quote Modify Modify

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.
« Last Edit: Jan 20th, 2009, 2:14am by Grimbal » IP Logged
nks
Junior Member
**





   
Email

Gender: male
Posts: 145
Re: iterative binary tree traversal  
« Reply #7 on: Jan 19th, 2009, 10:03pm »
Quote Quote Modify Modify

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.
IP Logged
cxwangyi
Newbie
*





   


Posts: 1
Re: iterative binary tree traversal  
« Reply #8 on: Dec 14th, 2012, 5:56am »
Quote Quote Modify Modify

#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;
}
IP Logged
anandg
Newbie
*





   


Posts: 1
Re: iterative binary tree traversal  
« Reply #9 on: Jan 8th, 2013, 9:43am »
Quote Quote Modify Modify

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-traversa l-without-using-stacks-or-recursion
 
// Made link usable --towr
« Last Edit: Jan 13th, 2013, 11:21am by towr » IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board