Siemens Interview Question
Software Engineer / Developersvoid iterativeTrav(struct node*root)
{
struct
{
struct node*ptr;
unsigned int vleft:1;
unsigned int vright:1;
}save[100];
int top=-1;
save[++top]=root;
while(top!=-1)
{
if(root->left!=NULL && !save[top].vleft )
{
save[top].vleft=1;
save[++top]=root->left;
root=root->left;
continue;
}
if(root->right !=NULL && !save[top].vright )
{
save[top].vright=1;
save[++top]=root->right;
root=root->right;
continue;
}
save[top].vleft=0;
save[top].vright]=0;
root=save[top--].ptr;
print root->data;
}
return;
}
Just use a stack to store the values of the node to be printed as well as its children. Store some meta data to indicate a node which has to be just printed. Hence after evaluating the left and right children of a node colour the node black. And after printing the node pop it off the stack.
- aadi June 12, 2007