InMobi Interview Question
Software Engineer / DevelopersTeam: InMobi
Country: India
Interview Type: In-Person
public void TraverseInOrder(treenode root)
{
Stack<treenode> stack = new Stack<treenode>();
treenode cur = root;
while(true)
{
if(cur != null)
{
stack.push(cur);
cur = cur.left;
}
else
{
if(stack.empty())
return;
cur = stack.pop();
//do your job here, print, eat or whatever
cur = cur.right();
}
}
}
void InOrderTraversal(BinaryTree *root)
{
stack<BinaryTree*> s;
s.push(root);
while (!s.empty())
{
BinaryTree *top = s.top();
if (top != NULL)
{
if (!top->visited)
{
s.push(top->left);
} else {
cout << top->data << " ";
s.pop();
s.push(top->right);
}
}
else
{
s.pop();
if (!s.empty())
s.top()->visited = true;
}
}
}
Morris algorithm -
1. Initialize current as root
2. While current is not NULL
If current does not have left child
a) Print current’s data
b) Go to the right, i.e., current = current->right
Else
a) Make current as right child of the rightmost node in current's left subtree
b) Go to this left child, i.e., current = current->left
- nihaldps February 22, 2012