Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
This should do:
bool IsMirror(Node* me, Node* myMirror)
{
return (
(me != NULL && myMirror != NULL) &&
(me.Value == myMirror.Value) &&
IsMirror(me->Left, myMirror->Right) &&
IsMirror(me->Right, myMirror->Left) &&
);
}
int isSymmetric( struct Node *root1, struct Node *root2 )
{
if( root1 == NULL && root2 != NULL || root1 != NULL && root2 == NULL )
return 0;
if( root1 == NULL && root2 == NULL )
return 1;
if( root1->val != root2->val )
return 0;
if( isSymmetric( root1->left, root2->right ) && isSymmetric( root1->right, root2->left ) )
return 1;
else
return 0;
}
The recursive solution is straight forward. But to do this non recursively, you need to verify two sets of straight and mirrored traversals are the same - we check pre-order and post order here.
bool CheckMirroringRecursive( NODE tree1, NODE tree2 )
{
if( tree1 == NULL && tree2 != NULL )
return false;
if( tree1 != NULL && tree2 == NULL )
return false;
if( tree1->data != tree2->data )
return false;
return CheckMirroringRecursive(tree1->left, tree2->right) && CheckMirroring(tree1->right, tree2->left)
return false;
}
bool CheckMirroringNonRecursive( NODE tree1, NODE tree2 )
{
_stack stack1, stack2;
NODE temp;
NODE nextPreOrderNode = NULL, nextInOrderNode = NULL;
do
{
nextPreOrderNode = NextPreOrderSuccessor(tree1, stack1, true);
nextInOrderNode = NextInOrderSuccessor(tree2, stack2, temp, true);
if( nextPreOrderNode == NULL && nextInOrderNode != NULL )
return false;
if( nextPreOrderNode != NULL && nextInOrderNode == NULL )
return false;
if( nextPreOrderNode->data != nextInOrderNode->data != NULL )
return false;
}while( nextPreOrderNode != NULL && nextInOrderNode =! NULL );
return true;
}
NODE NextPreOrderSuccessor( NODE &p, _stack &stack, bool mirror/*=false*/ )
{
if( p != NULL)
{
stack.push(p);
p = (mirror)?p->right:p->left;
return stack.top();
}
while( !stack.empty() )
{
temp = stack.pop();
if( ((mirror)?temp-?left:temp->right) != NULL )
p = mirror?temp->left:temp->right;
break;
}
if( p == NULL || stack.empty() )
return NULL; // end of traversal
}
NODE NextInOrderSuccessor( NODE &p, _stack &stack, NODE &lastVisited, bool mirror/*=false*/ )
{
if( p != lastVisited )
while( p!=NULL )
stack.push(p);
p = mirror?p->right:p->left;
if( !stack.empty() )
{
temp = stack.pop()
lastVisited = temp;
if( mirror?temp->left:temp->right )
p = mirror?temp->left:temp->right;
return temp;
}
if( p == NULL && stack.empty() )
return NULL; // end of traversal
}
- hello world February 16, 2012