wu :: forums « wu :: forums - iterative binary tree traversal » Welcome, Guest. Please Login or Register. Sep 7th, 2024, 10:08am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    cs (Moderators: ThudnBlunder, Eigenray, william wu, SMQ, Icarus, Grimbal, towr)    iterative binary tree traversal « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: iterative binary tree traversal  (Read 11971 times)
nitiraj
Newbie

Posts: 11
 iterative binary tree traversal   « on: Nov 14th, 2008, 1:47pm » Quote 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.

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:
Posts: 13730
 Re: iterative binary tree traversal   « Reply #1 on: Nov 14th, 2008, 2:43pm » Quote 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 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,
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:
Posts: 7527
 Re: iterative binary tree traversal   « Reply #3 on: Nov 15th, 2008, 2:13am » Quote 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 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
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 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:
Posts: 7527
 Re: iterative binary tree traversal   « Reply #6 on: Jan 15th, 2009, 6:40am » Quote 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

Gender:
Posts: 145
 Re: iterative binary tree traversal   « Reply #7 on: Jan 19th, 2009, 10:03pm » Quote 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 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 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