Author 
Topic: iterative binary tree traversal (Read 6530 times) 

nitiraj
Newbie
Posts: 11


iterative binary tree traversal
« on: Nov 14^{th}, 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.45 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: 12999


Re: iterative binary tree traversal
« Reply #1 on: Nov 14^{th}, 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 14^{th}, 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 14^{th}, 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 nonrecursive 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.45 : Write an O(n)time nonrecursive procedure that, given an nnode 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 14^{th}, 2008, 5:25pm by nitiraj » 
IP Logged 



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 6950


Re: iterative binary tree traversal
« Reply #3 on: Nov 15^{th}, 2008, 2:13am » 
Quote Modify

on Nov 14^{th}, 2008, 5:17pm, nitiraj wrote:p>RightChild = q ; ... p>LeftChild = q ; 
 It does modify the tree.

« Last Edit: Nov 15^{th}, 2008, 2:13am by Grimbal » 
IP Logged 



nitiraj
Newbie
Posts: 11


Re: iterative binary tree traversal
« Reply #4 on: Nov 16^{th}, 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 15^{th}, 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: 6950


Re: iterative binary tree traversal
« Reply #6 on: Jan 15^{th}, 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 20^{th}, 2009, 2:14am by Grimbal » 
IP Logged 



nks
Junior Member
Gender:
Posts: 145


Re: iterative binary tree traversal
« Reply #7 on: Jan 19^{th}, 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 14^{th}, 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 



