Amazon Interview Question
Software Engineer / DevelopersApproach I could think of:
1) Find Mirror of the Given Tree
2) Now traverse both the trees in order and store traversal in a string
3) Say you get traversal string str1 and st2
4) If str1 is reverse of str2 then the tree is valid mirror, else otherwise
Does this Q mean that tree is bilateral? if yes.
bool BilateralTree(node* root)
{
if(root == null)
return false;
return isTreeBilateral(&root, &root);
}
bool isTreeBilateral(node *root, node *root1)
{
if(!root && !root1)
return true;
if((!root && root1) || (root && !root1))
return false;
return isTreeBilateral(root->left, root1->right) && isTreeBilateral(root->right, root1->left);
}
Does you last call actually is
isTreeBilateral(root->left, root1->right) && isTreeBilateral(root->right, root1->left);
or (rather it should be)
isTreeBilateral(root->left, root1->left) && isTreeBilateral(root->right, root1->right);
or I have misunderstood the question?
It is the description of the question that sucks..... the example cannot show whether we check left-left & right-right or left-right & right-left.....
I think the original one:
isTreeBilateral(root->left, root1->right) && isTreeBilateral(root->right, root1->left) is more likely valid.
Cuz we suppose the "mirror" stands for the left of the left should be opposite the right of the right. root refers to left and root1 refers to right.
Am I right? This code sounds good but I am not pretty sure....I'd better run it this evening to make sure...
If the Tree is represented by string, we can do a simple check.
1. find beginning pos(close) of left tree --> f
2. find ending pos(close) of right tree ---> r
3. while( str[f] != '(' or ',' or ')' ) f++;
4. while( str[r] != '(' or ',' or ')' ) r--;
5. if( str[f] == '(" && str[r] == ')' ) {f++,r--};
6. else if( str[f] == ')' && str[r] == '(' ) {f++,r--};
7. else if( str[f] == str[r] == ',' ) {f++,r--};
8. else return false;
9. if( f >= r ) return true;
10. if( f < r ) goto 3;
bool checkMirror(Node * root)
{
if(root->left != null && root->right != null)
{
if(root->left = root->right) {
return ( checkMirror(root->left) && checkMirror(root->right) )
}
else {
return false;
}
}
else if(root->left = null && root->right = null)
{
return true;
}
else
return false;
}
@ ^ u cant check whether left tree then right tree "AND" them to get result cos try this case a root,root left(l),root right(r),l right,r left wud return false by ur code....An approach wud be to do inorder traversal to flatten the tree (with place holders even for null pointers)and to check the string for palindrome
1)Take two pointers to "root" of the tree say temp1,temp2;
2)Now first pointer "temp1" traverses tree in "preorder" and "temp2" in "postorder"..
till they reach the "root"(No need of complete preorder and postorder traversals)..
3)temp1 and temp2 at each and every node they visit check that either both are NULLs or both are NOTNULL..
i.e either if((temp1==NULL&&temp2==NULL)||(temp1!=NULL&&temp2!=NULL))
if the above condition fails tree is "not image" else "YES"
#include <stdio.h>
// DS for tree node
struct tnode {
int data;
struct tnode *left, *right;
};
// tree
typedef struct {
struct tnode *root;
} Tree;
// create a new node
struct tnode *newNode(int data, struct tnode *l, struct tnode *r) {
struct tnode *node = (struct tnode *) malloc(sizeof(struct tnode));
node->data = data;
node->left = l;
node->right = r;
return node;
}
// utility function - builds a mirrored tree
// comment any node for non-mirror
Tree* buildTree() {
Tree *t = (Tree *) malloc(sizeof(Tree));
t->root = newNode(1, NULL, NULL);
t->root->left = newNode(2, NULL, NULL);
t->root->left->left = newNode(3, NULL, NULL);
t->root->left->right = newNode(4, NULL, NULL);
t->root->right = newNode(5, NULL, NULL);
t->root->right->left = newNode(6, NULL, NULL);
t->root->right->right = newNode(7, NULL, NULL);
return t;
}
// Compare if left and right subtrees are mirrors
int isMirror(struct tnode *t1, struct tnode *t2) {
if(t1==NULL || t2==NULL)
return t1==t2;
return isMirror(t1->left, t2->left) && isMirror(t1->right, t2->right);
}
int main() {
Tree *t = buildTree();
printf("%s\n", isMirror(t->root->left, t->root->right) ? "Mirror" : "Non-Mirror");
return 0;
}
(A (B (C,D), E( F,G)))
1. remove root and outer parenthesis, we get B (C,D), E( F,G)
2. locate length/2 to see if it's a ',', return false if not
3. use 2 pointers starts at each parts, ->B and ->E
4. pass if both pointing to characters(need not to be the same) or '(' or ')' or ',', else return false
5. if first got length/2 and second got end, return true
complexity is O(n)
Simple java code:
public static boolean isMirror(BinaryTree tree1, BinaryTree tree2){
boolean isMirror=false;
if(tree1.getRoot()==null&&tree2.getRoot()==null) return true;
if(tree1.getRoot()==null||tree2.getRoot()==null) return false;
if(!tree1.getRoot().equals(tree2.getRoot())) return false;
isMirror=checkMirror(tree1.getRoot(),tree2.getRoot());
return isMirror;
}
private static boolean checkMirror(Node root1, Node root2) {
boolean isMirror=true;
if(root1.left!=null&&!root1.left.equals(root2.right)) return false;
if(root1.right!=null&&!root1.right.equals(root2.left)) return false;
if(root1.left!=null) isMirror=isMirror&&checkMirrorroot1.left,root2.right);
if(root1.right!=null) isMirror=isMirror&&checkMirror(root1.right,root2.left);
return isMirror;
}
can you elaborate with an example ?
- Anonymous January 22, 2011