## Amazon Interview Question for Software Development Managers

• 0

Country: India

Comment hidden because of low score. Click to expand.
4
of 4 vote

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).

``````bool 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);
}``````

Comment hidden because of low score. Click to expand.
0

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 ?

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
1
of 1 vote

This is a solution as well,

puddleofriddles.blogspot.com/2012/01/write-program-to-find-if-tree-is.html

Comment hidden because of low score. Click to expand.
0

Complexity if O(n).

Comment hidden because of low score. Click to expand.
1
of 1 vote

arungupta1.blogspot.in/

see the solution here

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

What is the complexity of this function

Comment hidden because of low score. Click to expand.
0

O(n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

This comment has been deleted.

Comment hidden because of low score. Click to expand.
0
of 0 vote

would be O(n) where n is the number of nodes.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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) ;
}

Comment hidden because of low score. Click to expand.
0

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)) ;
}

Comment hidden because of low score. Click to expand.
-2
of 2 vote

bool symmetric(node)
{
if(root == null)
return true;
else
return symmetric(node->left) && symmetric(node->right);
}

Comment hidden because of low score. Click to expand.
0

isn't it right answer? why -1 for this?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.