Is binary tree symmetric

© Parineeth M R

Question 14. Find if a binary tree is symmetric


A binary tree is symmetric, if the left sub-tree of each node is a mirror image of the right sub-tree. An example of a symmetric binary tree is given below

C/C++


int compare_nodes ( struct node *n1, struct node *n2) {
	if (!n1 && !n2)  /*If both the nodes are NULL */
		return 1;  /* return symmetric*/
	
	if ( (n1 && !n2) || (!n1 && n2)) /*If one node is NULL and other is not*/
		return 0; /*return not symmetric*/
	
	if (n1->data != n2->data) /*If data of two nodes don't match */
		return 0; /* return not symmetric */
		
	if (!compare_nodes (n1->left, n2->right)) 
		return 0;
	
	if (!compare_nodes (n1->right, n2->left)) 
		return 0;
	
	return 1; /*Return symmetric*/
}

/*Returns 1 if the tree is symmetric, 0 otherwise*/
int is_symmetric(struct node * root) {
	if (!root)
		return 1;
	
	return compare_nodes(root->left, root->right);
} 


Java


public static boolean compareNodes ( TreeNode n1, TreeNode n2) {
	if (n1 == null && n2 == null)  /*If both the nodes are null */
		return true;  /* return symmetric*/

	/*If one node is null and the other is not null*/
	if ( (n1 != null && n2 == null) || (n1 == null && n2 != null))  
		return false; /*return not symmetric*/

	if (n1.data != n2.data) /*If data of two nodes don't match */
		return false; /* return not symmetric */
	
	if (!compareNodes (n1.left, n2.right)) 
		return false;

	if (!compareNodes (n1.right, n2.left))
		return false;

	return true; /*Return symmetric*/
}

/*Returns true if the tree is symmetric, false otherwise*/
public static boolean isSymmetric(TreeNode root) {
	if (root == null)
		return true;

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



Python


@staticmethod
def compare_nodes(n1, n2): 
	if (not n1 and not n2):  #If both the nodes are None
		return True  # return symmetric

	#If one node is None and the other is not None
	if ( (n1 and not n2) or (not n1 and n2)):  
		return False #return not symmetric

	if (n1.data != n2.data): #If data of two nodes don't match
		return False # return not symmetric 
	
	if (not TreeNode.compare_nodes(n1.left, n2.right)): 
		return False

	if (not TreeNode.compare_nodes(n1.right, n2.left)): 
		return False

	return True #Return symmetric


@staticmethod
#Returns True if the tree is symmetric, False otherwise
def is_symmetric(root): 
	if (not root):
		return True

	return TreeNode.compare_nodes(root.left, root.right)