Problem Statement
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
Sample Test Cases
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
the following [1,2,2,null,3,null,3] is not:
1
/ \
2 2
\ \
3 3
Problem Solution
A tree is symmetric if the left subtree is a mirror reflection of the right subtree.
Two trees are a mirror reflection of each other if:
- Their two roots have the same value.
- The right subtree of each tree is a mirror reflection of the left subtree of the other tree.
We can use recursive approach to solve the problem.
We will go on recursively checking on the left and right half of the tree if there are equal or not, we can do this by using a helper function which will have root->left and root->right as its parameter. In this process, we will have three cases-
- If Both the left and the right subtree are NULL then we will return True.
- If anyone of them is NULL and the other is not this means they are not symmetrically equal to each other so we return false.
- If the value at particle node in the left subtree is not equal to the value in the right subtree then we have to return false.
Complexity Analysis
- Time complexity: O(n). Because we traverse the entire input tree once, the total run time is O(n), where n is the total number of nodes in the tree.
- Space complexity: The number of recursive calls is bound by the height of the tree. In the worst case, the tree is linear and the height is in O(n). Therefore, space complexity due to recursive calls on the stack is O(n)in the worst case.
Code Implementation
// C++ program to check if a given Binary Tree is symmetric or not
#include<bits/stdc++.h>
using namespace std;
// A Binary Tree Node
class TreeNode
{ public:
int val;
TreeNode* left, *right;
};
TreeNode *newNode(int key)
{
TreeNode *temp = new TreeNode;
temp->val = key;
temp->left = temp->right = NULL;
return (temp);
}
// Returns true if trees with roots as root1 and root2 are mirror
bool check(TreeNode*p,TreeNode*q)
{
if(p==NULL&&q==NULL) // case 1
{
return true;
}
if (p==NULL||q==NULL) // case 2
{
return false;
}
if(p->val!=q->val) // case 3
{
return false;
}
return check(p->left,q->right)&&check(p->right,q->left);
}
bool isSymmetric(TreeNode* root) {
bool x=check(root,root);
return x;
}
// Driver program
int main()
{
// Let us construct the Tree shown in the above figure
TreeNode *root = newNode(1);
root->left = newNode(2);
root->right = newNode(2);
root->left->left = newNode(3);
root->left->right = newNode(4);
root->right->left = newNode(4);
root->right->right = newNode(3);
cout << isSymmetric(root);
return 0;
}
class Node
{
int val;
Node left, right;
Node(int item)
{
val = item;
left = right = null;
}
}
class BinaryTree
{
Node root;
boolean symmetricHelper(Node root1, Node root2)
{
if (root1 == null && root2 == null)
return true;
if (root1 != null && root2 != null && root1.val == root2.val)
return (symmetricHelper(root1.left, root2.right)
&& symmetricHelper(root1.right, root2.left));
return false;
}
boolean isSymmetric(Node node)
{
return symmetricHelper(root, root);
}
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(2);
tree.root.left.left = new Node(3);
tree.root.left.right = new Node(4);
tree.root.right.left = new Node(4);
tree.root.right.right = new Node(3);
if (tree.isSymmetric(tree.root) == true)
System.out.println("Tree is symmetric");
else
System.out.println("Tree is asymmetric");
}
}
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def isMirror(root1 , root2):
if root1==None and root2==None:
return True
if (root1 != None and root2 != None):
if root1.val == root2.val:
return (isMirror(root1.left, root2.right) and isMirror(root1.right, root2.left))
return False
def isSymmetric(root):
return isMirror(root, root)
root = Node(1)
root.left = Node(2)
root.right = Node(2)
root.left.left = Node(3)
root.left.right = Node(4)
root.right.left = Node(4)
root.right.right = Node(3)
if isSymmetric(root):
print("Tree is symmetric")
else:
print("Tree is asymmetric")
