Check if the binary tree is mirrored or symmetrical

Question

What is the basis algorithm for testing if the tree is symmetrical. Since this is a binary tree, I would suggest that it will be a recursive definition of views

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 your chosen programming language, define the BTree class / C structure and its associated method to check if the tree is a mirror image. For statically typed languages, you can assume that node values ​​are integers.

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

Suppose the root of the tree is tracked by the caller and the isMirror () function is called on it.

Also, if you are defining a class, be sure to provide constructors with no arguments and getter / setter methods if data elements are not available.

Answer 1

How about calling mirrorEquals (root.left, root.right) for 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 the inverted right subtree, drawing an imaginary line of inversion through the root.

Answer 2

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 3

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

Look down each row of the tree and see if the values ​​are a palindrome. If all of them then, yes, it is a mirror. You will need to implement an algorithm to visit each row and include zero values ​​for rare trees. In pseudo code:

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

The trick is to develop an algorithm to iterate through the rows of a tree, given that sparse trees must have zero values ​​as place owners. This Java implementation looks fine:

 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; } } 

Answer 4

Recursive and iterative solutions in Java using the above approaches

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 5

EDIT

As noted in the comments, my first version of the algorithm failed for certain inputs. I am not going to reinvent the wheel, I just provide a response in Python using the correct @gvijay algorithm. First, the view 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 code above using all the tree samples in the question and trees that returned incorrect results, as indicated in the comments. Now the results are true 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 6

Here is the c ++ solution on 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 7

Below is a solution regarding 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 8

A slightly different approach.

How to do a crawl inside a binary tree that stores all the contents in some data structure, for example a string / array.

Once the crawl is complete, check if the elements in your array are a palindrome. Space is not so efficient (recursion takes O (log (n)), this method shows O (n)), but it will also work.

Answer 9

An iterative solution using a slightly different approach in python. Use queue1 to store left children in left-to-right order and queue2 to store children's rights in right-to-left order 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

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 11

If someone needs a Swift version, here is one.

Another approach would be to simply invert one of the subtrees and compare the two resulting subtrees in a simple way.

 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 12

I am not very experienced (only a year at corporate), but, in my opinion, this can be solved 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, 

Returns true if it matches.