Amazon Interview Question Software Development Managers
Country: India
can you elaborate on your soln ?
I am not use if I get this correctly:
suppose you have the following tree:
1
/ \
2 3
/ \
4 5
then i suppose your algo should return false because
of the condition (L! && R || L && R!)
should this only work for complete binary trees ?
Note that L and R have the same parent only in the first call of this function. After that, L and R are not the left and right children of a single node like you would do in a traditional traversal. After the root node, L and R are the symmetrically corresponding nodes from the left subtree of the root and right subtree of the root. Please think about this. The tree doesn't have to be balanced for this code to work and for your example, it returns true.
The calls look like this for your example:
IsSymmetric(1)
IsSymmetric(2,3) // children of the root
IsSymmetric(4,5) // 2->left and 3->right
IsSymmetric(NULL,NULL) // 4->left and 5->right
IsSymmetric(NULL,NULL) // 4->right and 5->left
IsSymmetric(NULL,NULL) // 2->right and 3->left
As you can see, the end result is true since none of the calls to IsSymmetric(Node* L,Node* R) have one NULL and one non-NULL argument.
This is a solution as well,
puddleofriddles.blogspot.com/2012/01/write-program-to-find-if-tree-is.html
Just trying to write a pseudo code:
bool Symmetric (struct node *rootl, struct node *rootr)
{
if (rootl == null) && (rootr == null)
{
return ( True);
}
if (((rootl) XOR (rootr) ) == 1 ) { return(False);}
if (((rootl->left) XOR (rootr->left)) == 0 ) && ((rootl->right) XOR (rootr->right)) == 0 )
{
Symmetric (rootl->Left, rootr->left);
Symmetric ( rootl->right, rootr->right);
}
Here we are passing the left and right node of the root of the given tree to the function.
Well, while being in the family of the O(n) algorithm, the answer is O(n/2) for the worst case scenario where the tree is indeed symmetric. We basically scroll through half of the nodes (on the left side for example) and compare where a counterpart in the same position exists on the other side.
If symmetric does not mean mirrored(right is mirror of left).
boolean checkSymmetric(Node node){
stack;
Node sym1,sym2;
sym1 = node.left;sym2=node.right;
while(true){
if(sym1!=null && sym2!=null){
stack.push(sym1.right);stack.push(sym2.right);
sym1=sym1.left;sym2=sym2.right;
}
else if(sym1==null && sym2==null){
if(stack.empty == true) return true;
else{
stack.pop(sym2);stack.pop(sym1);
}
}
else{
return false;
}
}
}
1
| |
2 3
| | |
4 5
Sorry , a silly mistake in previous post,
boolean checkSymmetric(Node node){
stack;
Node sym1,sym2;
sym1 = node.left;sym2=node.right;
while(true){
if(sym1!=null && sym2!=null){
stack.push(sym1.right);stack.push(sym2.right);
sym1=sym1.left;sym2=sym2.left;
}
else if(sym1==null && sym2==null){
if(stack.empty == true) return true;
else{
stack.pop(sym2);stack.pop(sym1);
}
}
else{
return false;
}
}
}
boolean isSymmetric (node *p1 , node *p2)
{
if (p1 == NULL && p2 == NULL)
return true;
else
return (isSymmetric(p1->left , p2->right) && isSymmetric(p1->right , p2->left) ;
}
boolean isSymmetric (node *p1 , node *p2)
{
if (p1 == NULL && p2 == NULL)
return true;
else if (( p1 == NULL && p2 != NULL ) || ( p1!=NULL && p2 == NULL))
return false ;
else
if (p1 != NULL && p2 != NULL)
return (isSymmetric(p1->left , p2->right) && isSymmetric(p1->right , p2->left)) ;
}
We need to check the left child of the left node, with the right child of the right node and vice versa. Complexity is O(n).
- crdmp January 10, 2012bool IsSymmetric(Node* r) { if ( r == NULL ) return true; return IsSymmetric(r->left, r->right); } bool IsSymmetric(Node* L, Node* R) { if ( !L && !R ) return true; if ( !L && R || L && !R ) return false; return IsSymmetric(L->left, R->right) && IsSymmetric(L->right, R->left); }