Amazon Interview Question Software Engineer in Tests
1of 1 voteWAP to check a tree is symmetric.
Need to check NULL
bool isSymmetric(Node *r1, Node *r2)
{
if (r1 == NULL && r2 == NULL)
return true;
if (r1 == NULL || r2 == NULL)
return false;
return (r1->data == r2->data && isSymmetric(r1->left, r2->right) && isSymmetric(r1->right, r2->left));
}
i little confused here !! whether u people understood the question wrong or the myself! here tree is symmetric means its mirror image should be exactly the same as the tree.
but you people writing code to test whether r1 and r2 are mirror images rather than testing they should be same.
i.e r1.left,r2.left should be same,similarly r1.right,r2.right should be same.indirectly it says that the tree's left and right subtrees should be mirror images.
Create a mirror image of the tree and then check whether the original tree is equal to the mirror image. If both the trees are equal then the tree is symmetric
private static boolean chksym(BTreeNode r1, BTreeNode r2) {
// TODO Auto-generated method stub
if((r1.left==null&&r2.right==null)&& (r1.right==null&&r2.left==null)||(r1.left==null&&r2.right==null)||(r1.right==null&&r2.left==null))
return true;
else if(r1.left==null&&r2.right==null&&r1.right!=null&&r2.left!=null)
return ((r1.right.val==r2.left.val)&&(chksym(r1.right,r2.left)));
else if(r1.right==null&&r2.left==null&&r1.left!=null&&r2.right!=null)
return ((r1.left.val==r2.right.val)&&(chksym(r1.left,r2.right)));
else if((r1.left!=null&&r2.right!=null)&& (r1.right!=null&&r2.left!=null)&&(r1.left!=null&&r2.right!=null)&&(r1.right!=null&&r2.left!=null))
return ((r1.left.val==r2.right.val)&&(r1.right.val==r2.left.val)&&(chksym(r1.left,r2.right))&&(chksym(r1.right,r2.left)));
else return false;
}
chkSim(root r1,root r2)
- Anonymous August 07, 2011{
return (r1->left.data==r2->right.data)&&
(r2->left.data==r1->right.data)&&
chkSim(r1->left,r2->right)&&
chkSim(r1->right,r2->left)
}