Amazon Interview Question Software Engineer / Developers
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
using namespace std;
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
vector <int> v;
int index=0;
/* Given a binary tree, print its nodes in inorder*/
void Preorder(struct node* node)
{
if (node == NULL)
return;
v.push_back(node->data);
index++;
/* then recur on left sutree */
Preorder(node->left);
/* now recur on right subtree */
Preorder(node->right);
}
/* Driver program to test above functions*/
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(2);
root->left->left = newNode(3);
root->left->right = newNode(4);
root->right->left = newNode(3);
root->right->right = newNode(4);
Preorder(root);
int sym=0;
for(int i=1;i<index;i++)
{
sym ^= v[i];
}
if( !sym ) cout<< "symmetric"<<endl;
else cout<<" NOT Symmetric "<<endl;
getchar();
return 0;
}
How can xoring all elts determine symmetricity???
consider this
1
2 3
3 2
I believe it should be BFS and not DFS for this q...
I think this code having something wrong ..
I think after XORing .. if the 'sym' equal to the "root value" it would be semetric .. otherwise it is not.
boolean isSymetry(Node root) {
return isSymetry(root.right, root.left);
}
boolean isSymetry(Node n1, Node n2) {
if(n1 == null && n2 == null) {
return true;
}
if(n1 != null && n2 != null) {
return n1.data == n2.data && isSymetry(n1.right, n2.left) && isSymetry(n1.left, n2.right);
}
return false;
}
This won't work bcoz.. the algorithm just compares nodes left and right children.. we need to check for symmetry for all the node in a given level... only thing i can think of is to check if the in-order traversal string is palindrome..
Hi Coward,
Can you please explain why it wont work. I am not clear on the part where the algorithm checks for symmetry on a level
yeah, thanks for sharing the pseudocode.
Coward, could you give some example where the logic would fail?
it wont work with any case....
see this 1
2 2
3 3 4 4
in ur code this will symmetric but in reality it is not ..
I think we need to enhance your logic with
depth of left subtree == depth of right subtree &&
preorder traversal should be a palindrome
Algorithm:
1. Traverse the tree in in-irder traversal & generate string.
2. Check the string created above is palindrome or not. If it is palindrome then then tree is a symmetric.
This approach does not work because Inorder in itself does not lead to unique tree structure. eg
1
2 5
3 2 3
4 5 4
has inorder as 435212534 which is a paindrome but the tree is nowhere near symmetric
Two solutions:
1. BFS, and put a delimiter after the nodes on each level. So when one level is done check if its next level is mirror.
2. Besides the root. if the tree is symmetric, then its left subtree should be identical to its right subtree. The problem becomes: checking if two trees are identical or not. Which can be done easily (e.g. pre-order traverse the two subtrees at the same time).
Your Solution is right, but i think it needs slight modification... think of such a case:
1
2 2
3 3
The 3rd level is symmetric on its own, but overall, tree is not...
we can change your solution slightly to cater such cases. whenever you encounter a NULL, put some known character, say -1 in case of tree with +ve integers. We can stop the algorithm if we see a case of non symmetry or get a Layer with all -1's !!
Here is my code
- gulusworld1989 February 11, 2011booolean isSymmetric(node n) { return isMirrorImage(n,n); } boolean isMirrorImage(node n1,node n2) { if(n1==null && n2==null) return true; else if(n1!=null || n2!=null) return false; else if(n1.val !=n2.val) return false; else return isMirrorImage(n1.left,n2.right) && isMirrorImage(n1.right,n2.left); }