Check if a binary tree is the mirror image of itself

Given a binary tree, how do we write a program to check if it is the mirror image of itself. This binary tree is also called a symmetric tree.

A binary tree is called a symmetric tree if it’s left and right sub-trees are mirror images of each other.

For example Let us consider the following examples of some symmetric and asymmetric trees.

    1
   / Symmetric
2 2

    1
   / Asymmetric
2   3

      1
     /
    2   2 Symmetric
   /
3       3

We can design a recursive algorithm like the following.

An empty tree is a symmetric tree.
At each node we check the following
1. If the left value and right value are same
2. If the left sub-tree of left node and right sub-tree of the right node are mirror images
3. If the right sub-tree of left node and left sub-tree of the right node are mirror images
If all the above conditions are satisfied then the tree is symmetric.

Here is the C++ implementation of this.

	#include <iostream>

	using namespace std;

	//Binary tree node type
	struct TreeNode
	{
	int val;
	TreeNode left, right;
	TreeNode(int v):val(v),left(NULL), right(NULL)
	{
	}
	};

	bool mirror_equals(TreeNode left, TreeNode right)
	{
	if( left == NULL \|\| right == NULL )
	return left == NULL && right == NULL;
	return (left->val == right->val &&
	mirror_equals(left->left, right->right) &&
	mirror_equals(left->right, right->left) );
	}
	bool is_symmetric(TreeNode *root)
	{
	if( root == NULL )
	return true;
	if( mirror_equals(root->left, root->right) )
	return true;
	return false;
	}

	void Test1()
	{
	TreeNode *root = new TreeNode(1);
	root->left = new TreeNode(2);
	root->right = new TreeNode(2);
	root->left->left = new TreeNode(3);
	root->right->right = new TreeNode(3);
	if(is_symmetric(root))
	{
	cout << "Symmetric" << endl;
	}
	else
	{
	cout << "Not symmetric" << endl;
	}

	}

	void Test2()
	{
	TreeNode *root = new TreeNode(1);
	root->left = new TreeNode(2);
	root->right = new TreeNode(2);
	root->left->left = new TreeNode(3);
	root->left->right = new TreeNode(3);
	if(is_symmetric(root))
	{
	cout << "Symmetric" << endl;
	}
	else
	{
	cout << "Not symmetric" << endl;
	}

	}
	int main()
	{
	Test1();
	Test2();
	return 0;
	}

by GitHub