Google Interview Question Software Engineer in Tests
it's the same thing
In that case u can call the above function as
isMirror(n,n)
where n is the root of the required node
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;
// it should also chekc the node's values, which was actually missing!
return isMirrorImage(n1.left,n2.right) && isMirrorImage(n1.right,n2.left) && (n1.value==n2.value);
}
hello, can anybody explain what does mirror image of tree means?? please give example. I am not aware of this term in tree.
Use any traversal algorithm, e.g. inorder, to traverse the tree. Now traverse the tree using the same algorithm except that whenever we follow node.left in the original algorithm we follow node.right instead. Perform both traversal in lock-step on the tree and at each step check to see if both traversals are making exact opposite turns (e.g. if traversal 1 makes a node.left turn, traversal2 makes a node.right turn) If there is one mismatched turn then return false else return true.
static string Traversal1(Node c)
{
string retVal = string.Empty;
if (c.left != null)
{
retVal = retVal + "l";
retVal = retVal + Traversal1(c.left);
}
if (c.right != null)
{
retVal = retVal + "r";
retVal = retVal + Traversal1(c.right);
}
return retVal;
}
static string Traversal2(Node c)
{
string retVal = string.Empty;
if (c.right != null)
{
retVal = retVal + "r";
retVal = retVal + Traversal2(c.right);
}
if (c.left != null)
{
retVal = retVal + "l";
retVal = retVal + Traversal2(c.left);
}
return retVal;
}
static bool IsMirrorImage(Node root)
{
string s1 = Traversal1(root);
string s2 = Traversal2(root);
s2.Replace("l", "x");
s2.Replace("r", "l");
s2.Replace("x", "r");
if (string.Compare(s1, s2) == 0)
{
return true;
}
else
{
return false;
}
}
Take INORDER traversals of both the binary trees and make 2 strings out of them.
Reverse one string and do a string match on the other. If they match then the 2 binary trees are mirror images of each other.
Tried this with few scenarios and it works.
Why wouldn't this work? Please post your comment with an example of a tree, its mirror and INORDER traversals under a case where this doesnt work.
Sorry, the solution I went with took two root nodes and determined if they are mirror images of each other, which would not work in the above example if using inorder traversals.
Inorder traversal won't work in the example below:
1
/ \
2 3
/ /
3 2
Mostly the same as soln by gulusworld1989
boolean isMirrorOfItself(Node r)
{
if ( r ==null ) {
return true;
}
return isMirror(r.left, r.right);
}
boolean isMirror(Node l, Node r)
{
// both are null
if (l==null && r == null) {
return true;
}
// only one is null
else if (r ==null || l ==null || r.value != l.value) {
return false;
}
return isMirror(l.left, r.right) && isMirror(l.right, r.left);
}
Do Simple DFS and check at each righ & left childs
public boolean checkMirror(Node root)
{
List<Node> queue = new LinkedList<Node>();
queue.add(root);
while(queue.isEmpty() == false)
{
Node n = queue.remove();
Node l = n.left();
Node r = n.right();
if((l == null && r != null) ||
(l != null && r == null))
return false;
if(l != null && r != null)
{
if( l.val() != r.val()) return false;
queue.add(l);
queue.add(r);
}
}
return true;
}
- gulusworld1989 October 17, 2010boolean 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; return isMirrorImage(n1.left,n2.right) && isMirrorImage(n1.right,n2.left); }