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.
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: 
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,
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:
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
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 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print