Aruba Networks

www.arubanetworks.com
Employer Engaged

Interview Question

Staff Software Engineer Interview Sunnyvale, CA

Binary search tree traversal without recursion (parent

  pointer provided)?
Answer

Interview Answer

1 Answer

0

use stack for iteratively going through nodes.

//Stack S;
While(1)
{

while(root)
{
    //print root->data
   push (S,root);
   root = root->left;

}
if(isemptystack(S)
 return;

root = Pop(S);
//after left subtree, goto right subtree
root = root->right;

}

Student123 on Oct 15, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.