Microsoft Interview Question
Software Engineer in TestsFor some reason my first reaction was to use a queue and do it non recursive.
Queue q;
q.add(root)
while(!Q.empty())
{
node* top = q.pop();
if (top->right && top->left)
{
// connect rt to left
}
if (top->left)
q.add(top->left)
if (top->right)
q.add(top->right)
}
same complexity in terms of space...we use explict queue here instead of recursion stack
Anonymous on January 01, 2009 is right
I think interviewer must expecting that right pointer should be used to point to sibling otherwise this problem becomes very simple.
Here is my solution --- initially function shd be called by passing NULL as sibling value as root has no sibling. and at each subsequent node, remove right pointer and make it to point to sibling of given node. also you will need to store value of actual right subtrees pointer before doing this.
Caller :- covertToLeftSibling(root, NULL);
Function definition-
covertToLeftSibling(Node root, Node sib)
{
Node t= NULL;
if(!root)
return;
else
{
if(root->left && root->right)
{
t= root->right;
root->right =sib;
covertToLeftSibling( t, NULL );
covertToLeftSibling( root->left, t );
}
else
{ if(root->left)
{
root->right =sib;
covertToLeftSibling( root->left, NULL );
}
else
{
if(root->right)
{
root->left= root->right;
root->right =sib;
}
else
{
root->right =sib;
}
}
}
}
}
Here is my code:
Assuming my node structure is:
- Gaurav April 04, 2008