Amazon Interview Question
Software Engineer / Developersfor n-ary tree, do the same thing. Got N queues.
Always add NULL to the queues if a node does not exist
This func takes left & right child of a tree, which is going under symmetry consideration.
bool isSymmetricTree(node * ptr1, node * ptr2)
{
if(ptr1->value != ptr2->value)
return 0;
return ( ( ( ptr1->left != 0 && ptr2->left != 0 ) ? isSymmetricTree(ptr1->left, ptr2->left) : (ptr1->left == ptr2->left) )
&& ( ( ptr1->right != 0 && ptr2->right != 0 ) ? isSymmetricTree(ptr1->right, ptr2->right) : (ptr1->right == ptr2->right) ) );
}
I think the last line should change to return ( ( ( ptr1->left != 0 && ptr2->right != 0 ) ? isSymmetricTree(ptr1->left, ptr2->right) : (ptr1->left == ptr2->right) )
&& ( ( ptr1->right != 0 && ptr2->left != 0 ) ? isSymmetricTree(ptr1->right, ptr2->left) : (ptr1->right == ptr2->left) ) );
Because symmetric means mirroring , the left sub tree should mirror the right sub tree.
}
How about creating in-order, postorder or preorder traversal output of left and right sub tree of root node and comparing all the elements one by one.
any thoughts???
We can also go for a diferent strategy.First we go for the in-order traversal of the Left subtree and push every node->data into a stack. Then we make and in-order traversal of the Right subtree and compare the data with the popped value of stack.If they don't match then the right subtree is not a mirror image of the left subtree and so tree isn't symmetric
We can also go for a diferent strategy.First we go for the in-order traversal of the Left subtree and push every node->data into a stack. Then we make and in-order traversal of the Right subtree and compare the data with the popped value of stack.If they don't match then the right subtree is not a mirror image of the left subtree and so tree isn't symmetric
// pass root->left and root->right in this function
bool Symmetric_tree(node *ptr1,node *pt2)
{
if(!ptr1 && !ptr2)
return(true);
if(!ptr1)
return(false);
if(!ptr2)
return(false);
return((ptr1->data == ptr2->data)&&Symmetric_tree(ptr1->left,ptr2->right)&&Symmetric_tree(ptr1->right,ptr2->left))
}
From main call the function isSymmetric1 with the root node as argument
bool isSymmetric1 (Node *root)
{
if (root == NULL)
return true;
for (int i = 0, int j = root->no_of_children - 1; i < j; i++, j--)
{
if (!isSymmetric2 (a->children[i], a[children[j])
return false;
}
return (i == j)? isSymmetric (a->children[i]): true;
}
bool isSymmetric2 (Node *p, Node *q)
{
if (p == NULL && q == NULL)
return true;
if ((p != NULL && q != NULL) && (p->info == q->info) && (p->no_of_children == q->no_of_children)
{
for(int i = 0, int j = no_of_children - 1; j >= 0; i++, j--)
{
if (!isSymmtrical2 (p->children[i], q->children[j])
return false;
}
return true;
}
return false;
}
from the root node, do the broad first seach for the two sub nodes. At each step, put the node into a queue. if a node is NULL, put NULL into the queue also.
- majun8cn October 02, 2009After that,we got two queques. Compare these two queues side by side. Return false when the two compared node are not equal. Return true at the end
Time: O(2*N) Space: O(2*N)