Check if a binary tree is a mirror image or symmetric

Joe Sars Grimaldi picture Joe Sars Grimaldi · Dec 8, 2011 · Viewed 42.2k times · Source

What is the basics algorithm for testing if a tree is symmetrical. Because it is a binary tree, I would assume that it would be a recursive definition of sorts

The formal question is below:

A binary tree is a mirror image of itself if its left and right subtrees are identical mirror images i.e., the binary tree is symmetrical. This is best explained with a few examples.

  1
 / \
2   2

TRUE

   1
  / \
 2   2
  \
   3

FALSE

     1
   /   \
  2     2
 / \   / \
4   3 3   4

TRUE

       1
     /   \
    2     2 
   / \   / \
  3   4 3   4

FALSE

       1
     /   \
    2     2
   /       \
  3         3

TRUE

In a programming language of choice, define a BTree class/C struct and an associated method to check if the tree is a mirror image. For statically typed languages, you can assume that node values are all integers.

Class/structure definition
BTree {
  BTree left;
  BTree right;
  int value;
}

Assume that the root of the tree is tracked by caller and function isMirror() is invoked on it.

Also, if defining a class, make sure to provide a no-argument constructor and getter/setter methods if data elements are not publicly accessible.

Answer

gvijay picture gvijay · Dec 8, 2011

How about calling mirrorEquals(root.left, root.right) on the following function :-

boolean mirrorEquals(BTree left, BTree right) {
  if (left == null || right == null) return left == null && right == null;
  return left.value == right.value
     && mirrorEquals(left.left, right.right)
     && mirrorEquals(left.right, right.left);
}

Basically compare the left subtree and inverted right subtree, drawing an imaginary line of inversion across root.