Sunday, March 9, 2014

Inorder traversal of binary tree w/o recursion

Problem:
Inorder traversal of binary tree w/ recursion

Solution:

/* Iterative method using stack */
Inordertraversal(struct btree *root)   
{
 while(1)
 {   
  while( root )
  {
   push(root);
   root = root->left;
  }
  if(Isstackempty(S))
   return;
  printf( S(top)->data);
  root = pop(S);
  root = root->right;
 }
}

Complexity:
time - O(n)
space - O(n)
Links and credits:
http://www.careercup.com/question?id=5198302274387968

No comments:

Post a Comment