Check if a binary tree is a mirror image or symmetric

Question

What is the basic 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 1

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def is_mirror(t1,t2):
            # this is when I hit the leaf nodes
            if t1 is None and t2 is None:
                return True
            # if node has only one child
            if t1 is None or t2 is None:
                return False
            return t1.val==t2.val and is_mirror(t1.left,t2.right) and is_mirror(t1.right,t2.left)
        return is_mirror(root.left,root.right)

Answer 2

how about a java script solution

algorithm used

araay = ["10" , "2", "2", "#", "1", "1", "#"] lets break this into each step

step 1 = ["10"]
step 2 = [ "2", "2" ]
step 3 = ["#", "1", "1", "#"]

check mirror for each step other than first step

lets take step 3 . step 3 = ["#", "1", "1", "#"] break this into 2 array from middle

step 3 1 = ["#", "1" ]
step 3 2 = ["1", "#"]

Now reverse step 3 2

step 3 2 = ["1", "#"]

now check if step 3 2 is equal to step 3 1

Do the above thing for each step

if all are mirror then binary tree is mirror

const Input = ["10" , "2", "2", "#", "1", "1", "#"];
function isEqual(a,b)
{
  // if length is not equal
  if(a.length!=b.length)
   return false;
  else
  {
  // comapring each element of array
   for(var i=0;i<a.length;i++)
   if(a[i] !== b[i]){
    return false;
   }
    return true;
  }
}

// Response 
let symetric = true ;
let stepSymetric = true ;
let mirror = true ;
// length of input 
const length = Input.length ;
// const length = 31 ;

// lets create binary tree from it

const totalSteps =
      Math.log(length + 1)/Math.log(2) ;

// check for symetric binary tree
function checkInt(n) { return parseInt(n) === n };
 symetric = checkInt(totalSteps);

//now check for mirror
let goneArrayLength = 0 ;
for (let i = 0; i < totalSteps; i++) { 
  const cStep = Math.pow(2,i);
  
  const stepArray = [];
  // console.log(goneArrayLength);
  
  // now update the step array 
  const start = goneArrayLength ;
  const end =  goneArrayLength + cStep ;
  
  for (let j = start; j < end; j++) {
    stepArray.push(Input[j])
  }
  
  console.log(stepArray);
  // Now we have each step lets find they are mirror image or not
  // check for even length
  if(stepArray.length%2 !== 0 && i !== 0){
    stepSymetric = false ;
  }
  const partitation = stepArray.length / 2 ;
  const leftArray = stepArray.slice(0,partitation);
  const rightArray = stepArray.slice(partitation , partitation * 2);
  // console.log("leftArray");
  // console.log(leftArray);
  // console.log("rightArray");
  // console.log(rightArray);
  function mirrorCheck (){
    let check = false;
    if(cStep === 1){
      return true ;
    }
    let array1 = leftArray;
    let array2 = rightArray.reverse();
    // console.log("first");
    // console.log(array1);
    // console.log("second");
    // console.log(array2);
   let equal = isEqual(array1 , array2)
   // console.log(equal);
    check = true ;
    if(!equal){
      // console.log("Noooooooooooooooo")
      check = false ;
    }
    
    return check;
  }
  let mirrorC = mirrorCheck();
  
  if(!mirrorC){
    mirror = false;
  }
  goneArrayLength = goneArrayLength + cStep ;
}
console.log(mirror + " " + symetric + " " + stepSymetric )

if(mirror && symetric && stepSymetric ){
  console.log("Mirror Image");
  
}
else{
  console.log("Not mirror image")
}
// console.log(isSymetric);
// console.log(totalSteps);

Answer 3

Using Queue , Because i find Recursion a bit hard.

bool isSymmetric(TreeNode* root) {
    queue<TreeNode*> q;
    q.push(root);
    q.push(root);
    while(q.empty()==false){
        TreeNode* a = q.front();
        q.pop();
        TreeNode* b = q.front();
        q.pop();
        if(a->val != b->val){
            return false;
        }
         if(a->left == nullptr and b->right != nullptr)
            return false;
        if(a->left != nullptr and b->right == nullptr)
            return false;
        if(a->right != nullptr and b->left == nullptr)
            return false;
        if(a->right == nullptr and b->left != nullptr)
            return false;
        if(a->left != nullptr and b->right != nullptr){
            q.push(a->left);
            q.push(b->right); 
        }
        if(a->right != nullptr and b->left != nullptr){
            q.push(a->right);
            q.push(b->left);
        }`enter code here`
    }
    return true;
}

Answer 4

public class SymmetricTree {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //int[] array = {1,2,2,3,4,4,3};
        /*
         *                  1
         *                 / \
         *                /   \
         *               /     \
         *              2       2
         *             / \     / \
         *            /   \   /   \
         *           3     4 4     3
         * 
         * */
        //int[] array = {1,2};
        BinaryTree bt=new BinaryTree();
        bt.data=1;
        bt.left = new BinaryTree(2);
        bt.right = new BinaryTree(2);
        bt.left.right = new BinaryTree(3);
        bt.right.right = new BinaryTree(3);
        //bt=BinaryTree.buildATree(bt, array);
        System.out.print(isSymmetric(bt));
        BinaryTree.inOrderTraversal(bt);
    }
    public static boolean isSymmetric(BinaryTree root){
        if(root==null)
            return true;
        return isSymmetricLR(root.left,root.right);
    }
    public static boolean isSymmetricLR(BinaryTree left, BinaryTree right){
        if(left == null && right == null)
            return true;
        if(left!=null && right!=null)
            return (left.data == right.data) &&
                    (isSymmetricLR(left.left, right.right)) &&
                    (isSymmetricLR(left.right, right.left));
        return false;
    }
}

Answer 5

Thought I'd add a solution in Python that some people might find easier to understand than other approaches. The idea is:

1. add +1 to value returned by left child.
2. add -1 to value returned by right child.
3. return l+r to parent

So if l+r == 0 for any node in the tree, then the sub-tree anchored at that node is symmetric. Therefore the entire tree is symmetric only if l+r == 0 at root.

def check(root):
    l = check(root.left)+1 if root.left else 0
    r = check(root.right)-1 if root.right else 0
    return l+r

def is_symmetric(root):
    return root is not None and check(root) == 0

Answer 6

using python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def helper(root1, root2):
            if not root1 and not root2: return True
            if not root1 or not root2: return False            
            if root1.val != root2.val: return False
            if helper(root1.left, root2.right): return helper(root1.right, root2.left)
            return  False
        return helper(root, root)

Answer 7

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.

Answer 8

If someone needs a Swift version, here's one.

Another approach would be to just invert one of the subtrees, and compare the two resulting subtrees in a straightforward manner.

func compareTrees(left: TreeNode?, right: TreeNode?) -> Bool {
    var res = false
    if left == nil && right == nil {return true}
    if left != nil && right != nil {
        res = left!.val == right!.val &&
              compareTrees(left!.left, right: right!.left) &&
              compareTrees(left!.right, right: right!.right)
    }
    return res
}

func invertTree(node: TreeNode?) {
    if node == nil {return}

    var tmp = node!.left
    node!.left = node!.right
    node!.right = tmp

    invertTree(node!.left)
    invertTree(node!.right)
}

// and run it as:
if root == nil {print("Y")}
invertTree(root!.right)
compareTrees(root!.left, right: root!.right) ? print("Y") : print("N")

Answer 9

Iterative solution using slightly different approach in python. Use queue1 to store left children in order of left to right and queue2 to store right children in order of right to left and compare for equality.

def isSymmetric(root):
    if not root:
        return True
    if not (root.left or root.right):
        return True
    q1 = collections.deque([root.left])
    q2 = collections.deque([root.right])
    while q1 and q2:
        n1 = q1.popleft()
        n2 = q2.popleft()
        if n1 is None and n2 is None:
            continue
        if (n1 is None) ^ (n2 is None):
            return False
        if n1.val != n2.val:
            return False
        q1.append(n1.left)
        q1.append(n1.right)
        q2.append(n2.right)
        q2.append(n2.left)
    if not (q1 and q2):
        return True
    return False

Answer 10

Below is the solution with respect to C- COde

isMirror(root)
{ 
Symmetric(root->left, root->right);
}

Symmetric(root1,root2)
{
 if( (root1->left EX-NOR root2->right) && (root1->right EX-NOR root2->left) && (root1->value==root2->value) )        
//exnor operation will return true if either both present or both not present 
// a EX-NOR b =(!a && !b) || (a && b))
        {
    Symmetric(root1->left, root2->right);
    Symmetric(root1->right, root2->left);
        }    
else return false;
}

Answer 11

Recursive and Iterative solutions in Java using approaches discussed above

Recursive

public Boolean isSymmetric(TreeNode root) {
    if (root == null) {
        return true;
    }

    return isSymmetricInternal(root.left, root.right);
}

private Boolean isSymmetricInternal(TreeNode leftNode,
        TreeNode rightNode) {

    boolean result = false;

    // If both null then true
    if (leftNode == null && rightNode == null) {
        result = true;
    }

    if (leftNode != null && rightNode != null) {
        result = (leftNode.data == rightNode.data)
                && isSymmetricInternal(leftNode.left, rightNode.right)
                && isSymmetricInternal(leftNode.right, rightNode.left);
    }

    return result;
}

Iterative using LinkedList as a Queue

private Boolean isSymmetricRecursive(TreeNode root) {
    boolean result = false;

    if (root == null) {
        return= true;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root.left);
    queue.offer(root.right);

    while (!queue.isEmpty()) {
        TreeNode left = queue.poll();
        TreeNode right = queue.poll();

        if (left == null && right == null) {

            result = true;

        }
        else if (left == null || 
                right == null || 
                left.data != right.data) {
            // It is required to set result = false here
            result = false;
            break;
        }

        else if (left != null && right != null) {
            queue.offer(left.left);
            queue.offer(right.right);

            queue.offer(left.right);
            queue.offer(right.left);
        }
    }

    return result;
}

Test Case

    @Test
public void testTree() {

    TreeNode root0 = new TreeNode(1);
    assertTrue(isSymmetric(root0));
    assertTrue(isSymmetricRecursive(root0));

    TreeNode root1 = new TreeNode(1, new TreeNode(2), new TreeNode(2));
    assertTrue(isSymmetric(root1));
    assertTrue(isSymmetricRecursive(root1));

    TreeNode root2 = new TreeNode(1,
            new TreeNode(2, null, new TreeNode(3)), new TreeNode(2));
    assertFalse(isSymmetric(root2));
    assertFalse(isSymmetricRecursive(root2));

    TreeNode root3 = new TreeNode(1, new TreeNode(2, new TreeNode(4),
            new TreeNode(3)), new TreeNode(2, new TreeNode(3),
            new TreeNode(4)));
    assertTrue(isTreeSymmetric(root3));
    assertTrue(isSymmetricRecursive(root3));

    TreeNode root4 = new TreeNode(1, new TreeNode(2, new TreeNode(3),
            new TreeNode(4)), new TreeNode(2, new TreeNode(3),
            new TreeNode(4)));
    assertFalse(isSymmetric(root4));
    assertFalse(isSymmetricRecursive(root4));
}

Tree Node class

public class TreeNode {

int data;

public TreeNode left;
public TreeNode right;

public TreeNode(int data){
    this(data, null, null);
}

public TreeNode(int data, TreeNode left, TreeNode right)
{
    this.data = data;
    this.left = left;
    this.right = right;
}
}

Answer 12

Solution 1 - Recursively:

bool isMirror(BinaryTreeNode *a, BinaryTreeNode *b)
{
    return (a && b) ?  
        (a->m_nValue==b->m_nValue 
        && isMirror(a->m_pLeft,b->m_pRight) 
        && isMirror(a->m_pRight,b->m_pLeft)) :  
    (a == b);
}
bool isMirrorItselfRecursively(BinaryTreeNode *root) 
{
    if (!root)
        return true;

    return isMirror(root->m_pLeft, root->m_pRight);
}

Solution 2 - Iteratively:

bool isMirrorItselfIteratively(BinaryTreeNode *root) 
{
    /// use single queue
    if(!root) return true;
    queue<BinaryTreeNode *> q;
    q.push(root->m_pLeft);
    q.push(root->m_pRight);
    BinaryTreeNode *l, *r;
    while(!q.empty()) {
        l = q.front();
        q.pop();
        r = q.front();
        q.pop();
        if(l==NULL && r==NULL) continue;
        if(l==NULL || r==NULL || l->m_nValue!=r->m_nValue) return false;
        q.push(l->m_pLeft);
        q.push(r->m_pRight);
        q.push(l->m_pRight);
        q.push(r->m_pLeft);
    }

    return true;
}

Answer 13

Slightly different approach.

How about do an inorder traversal of the binary tree storing all the contents in some data structure like a string/ array.

Once traversal is complete, check if the elements in your array form a palindrome. Not as efficient space wise (recursion takes O(log(n)), this method tales O(n)) but this will work as well.

Answer 14

I'm not very experienced (just a year at corporate), but in my opinion, this can be solved by using S=recursion

For example:

MYTREECLASS B1= new MYTREECLASS();
MYTREECLASS B2= new MYTREECLASS();
B1= OriginalTree;
B2=OriginalTRee;
Boolean CHECK(MYTREECLASS, MYTREECLASS)
{
if (B1.Node = B2.Node)
then (
CHECK(B1.Left, B2.Right);
CHECK(B1.Right,B2.Left)
)
elseIf(b1.Left==null or b2.right...blah blah ,,)
return False)
else return False,

Return true if it matches.

Answer 15

Here is a C++ solution per gvijay

bool isMirrorTree(BTnode* LP, BTnode* RP)
{
    if (LP == NULL || RP == NULL) // if either is null check that both are NULL
    { 
        return ( LP == NULL && RP == NULL );
    } 
    // check that data is equal and then recurse
    return LP->data == RP->data && 
           isMirrorTree( LP->left, RP->right ) && 
           isMirrorTree( LP->right, RP->left );
}

Answer 16

EDIT

As was pointed out in the comments, my first version of the algorithm failed for certain inputs. I'm not going to reinvent the wheel, I'll just provide a Python answer using @gvijay correct algorithm. First, a representation for the binary tree:

class BTree(object):
    def __init__(self, l, r, v):
        self.left  = l
        self.right = r
        self.value = v
    def is_mirror(self):
        return self._mirror_equals(self.left, self.right)
    def _mirror_equals(self, left, right):
        if left is None or right is None:
            return left is None and right is None
        return (left.value == right.value
                and self._mirror_equals(left.left, right.right)
                and self._mirror_equals(left.right, right.left))

I tested the above code using all the sample trees in the question and the trees which were returning incorrect results, as mentioned in the comments. Now the results are correct for all cases:

root1 = BTree(
    BTree(None, None, 2),
    BTree(None, None, 2),
    1)
root1.is_mirror() # True

root2 = BTree(
    BTree(None, BTree(None, None, 3), 2),
    BTree(None, None, 2),
    1)
root2.is_mirror() # False

root3 = BTree(
    BTree(
        BTree(None, None, 4),
        BTree(None, None, 3),
        2),
    BTree(
        BTree(None, None, 3),
        BTree(None, None, 4),
        2),
    1)
root3.is_mirror() # True

root4 = BTree(
    BTree(
        BTree(None, None, 3),
        BTree(None, None, 4),
        2),
    BTree(
        BTree(None, None, 3),
        BTree(None, None, 4),
        2),
    1)
root4.is_mirror() # False

root5 = BTree(
    BTree(BTree(None, None, 3), None, 2),
    BTree(None, BTree(None, None, 3), 2),
    1)
root5.is_mirror() # True

root6 = BTree(BTree(None, None, 1), None, 1)
root6.is_mirror() # False

root7 = BTree(BTree(BTree(None, None, 1), None, 2), None, 1)
root7.is_mirror() # False

Answer 17

The recursive solution from @gvijay is very clear, and here's an iterative solution.

Inspect each row of the tree from top to bottom and see if the values are a palindrome. If they all are then, yes, it's a mirror. You'll need to implement an algorithm to visit each row and include null values for sparse trees. In pseudocode:

boolean isMirror(BTree tree) {
  foreach (List<Integer> row : tree.rows() {
    if (row != row.reverse()) return false;
  }
  return true;
}

The trick is to design the algorithm to iterate the rows of a tree with consideration that sparse trees should have null values as place holders. This Java implementation seems ok:

public static boolean isMirror(BTree root) {
  List<BTree> thisRow, nextRow;
  thisRow = Arrays.asList(root);
  while (true) {
    // Return false if this row is not a palindrome.
    for (int i=0; i<thisRow.size()/2; i++) {
      BTree x = thisRow.get(i);
      BTree y = thisRow.get(thisRow.size()-i-1);
      if ((x!=null) && (y!=null)
          && (x.value != y.value))
        return false;
      if (((x==null) && (y!=null))
          || (x!=null) && (y==null))
        return false;
    }
    // Move on to the next row.
    nextRow = new ArrayList<BTree>();
    for (BTree tree : thisRow) {
      nextRow.add((tree==null) ? null : tree.lt);
      nextRow.add((tree==null) ? null : tree.rt);
    }
    boolean allNull = true;
    for (BTree tree : nextRow) {
      if (tree != null) allNull = false;
    }
    // If the row is all empty then we're done.
    if (allNull) return true;
    thisRow = nextRow;
  }
}