Home » Interview coding problems/challenges

Symmetric Tree

In this article, we are going to see how to find whether a tree is symmetric tree or not? This problem can be featured in the interview coding rounds.
Submitted by Radib Kar, on January 14, 2019

Problem statement:

Given a binary Tree, check whether the tree is symmetric or not.

Input Example:

For example
    1
   / \
  2   2
 / \ / \
3  4 4  3

The above tree is symmetric
    1
   / \
  2   2
   \   \
   4    4
The above tree is not

Solution

Symmetric tree

A binary tree is said to be symmetric, if a vertical axis through the root cuts the tree in two mirror subtrees. That means the right child & left child of root are two mirror trees.

Algorithm:

Earlier, we have discussed how two check mirror trees? Kindly refer there for more detailed analysis.

In this case we are to check whether the tree is symmetric or not, which can be done via checking whether root's children are mirror trees or not?

FUNCTION isSymmetric(Tree Node* root) 
    1.  Check for base cases
	    IF root==NULL //if root is NULL
            Return true;
	    IF root->left==NULL &&root->right==NULL //if both child is NULL
	        Return true;
	    IF root->left==NULL || root->right==NULL //if only one child is NULL
	        Return false;
    2.  check whether left & right subtrees are mirror of each other or not 
		Return check(root->left,root->right);
END FUNCTION

FUNCTION Check(Tree Node* root1, Tree Node* root2)
	a.  Check base cases
	    If root1==NULL && root2==NULL
	        Then it's mirror tree, return true;
	    If root1==NULL || root2==NULL
	        Then it's not a mirror tree, return false
	        Because one root is NULL whether another is not. 
	        (Both can't be NULL here, since already checked before) 
	    If root1->data != root2->data
	        Then it's not a mirror tree, return false.
	        Because roots are different & thus can't be mirror image of other
    b.  Recursively check for sub-trees
	    Return (Check (root1->left, root2->right) &&Check(root1->right,root2->left));
END FUNCTION

Example with explanation

For the example:
    1
   / \
  2   2
 / \ / \
3  4 4  3

At the main function:
It calls isSymmetric(1)
-----------------------------------------------------------

isSymmetric(1):
Base cases are not met
It calls check(1->left, 1->right)

Root1=2(1->left) and Root2=2(1->right)
It calls check (2, 2)
-----------------------------------------------------------

check (2, 2):
2->left =3 and 2->right=4 in case of tree1
2->left =4 and 2->right=3 in case of tree2
No base cases are satisfied thus it returns,
(check ( 3, 3) && check ( 4, 4))
Call to check ( 3, 3) and check ( 4, 4)
-----------------------------------------------------------

check (3, 3):(call at check (2, 2))
3->left =NULL and 3->right=NULL in case of tree1
3->left =NULL and 3->right=NULL in case of tree2
No base cases are satisfied thus it returns,
(check (NULL, NULL) &&check (NULL, NULL))
Call to check (NULL, NULL) and check (NULL, NULL))
-----------------------------------------------------------

check (4, 4): (call at check (2, 2))
4->left =NULL and 4->right=NULL in case of tree1
4->left =NULL and 4->right=NULL in case of tree2
No base cases are satisfied thus it returns,
(check (NULL, NULL) &&check (NULL, NULL))
Call to check (NULL, NULL) &&check (NULL, NULL)
-----------------------------------------------------------

check (NULL, NULL): (call at check (3, 3))
Base case matches and returns 1. 
-----------------------------------------------------------

check (NULL, NULL): (call at check (3, 3))
Base case matches and returns 1. 
-----------------------------------------------------------

check (NULL, NULL): (call at check (4, 4))
Base case matches and returns 1. 
-----------------------------------------------------------

check (NULL, NULL): (call at check (4, 4))
Base case matches and returns 1. 
-----------------------------------------------------------

Thus at isSymmetric(1),
check (2, 2) returns:
=   check ( 3, 3) &&check ( 4, 4)
=   ((check (NULL, NULL)&&check (NULL, NULL)) 
&&((check (NULL, NULL)&&check (NULL, NULL))
=   ((1 && 1)) && (1 && 1))
=   1

Thus at main it returns 1
So it's a symmetric tree

C++ implementation

#include<bits/stdc++.h>
using namespace std;

// TreeNode node type
class TreeNode{
	public:             
		int val;           //value
		TreeNode *left;    //pointer to left child
		TreeNode *right;   //pointer to right child
};

// creating new node
TreeNode* newnode(int data)  
{ 
	TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode)); 
	node->val = data; 
	node->left = NULL; 
	node->right = NULL; 

	return(node); 
}

// function to check mirror trees
bool check(TreeNode* root1,TreeNode* root2){
	// base cases
	//if both root is NULL, then it's mirror tree
	if(!root1 && !root2)
		return true;
	//if one is NULL & other is not
	//then it's not mirror tree
	if(!root1 || !root2)
		return false;
	//if root data are different it's not mirror tree
	if(root1->val!=root2->val)
		return false;
	//check for subtrees
	return (check(root1->left,root2->right)&&check(root1->right,root2->left));
}

bool isSymmetric(TreeNode* root) {
	//base cases
	if(!root)
		return true;
	if(!root->left && !root->right)
		return true;
	if(!root->left || !root->right)
		return false;
	//check whether left & right subtrees 
	//are mirror of each other or not 
	return check(root->left,root->right);
}

int main(){
	cout<<"tree is built as per example\n";
	
	TreeNode *root=newnode(1); 
	root->left= newnode(2); 
	root->right= newnode(2); 
	root->right->right=newnode(3);
	root->right->left=newnode(4);
	root->left->left=newnode(3); 
	root->left->right=newnode(4);

	if(isSymmetric(root))
		cout<<"It's a symmetric tree\n";
	else
		cout<<"It's not a symmetric tree\n";

	return 0;
}

Output

tree is built as per example
It's a symmetric tree