How to Check if a Binary Tree Is Symmetric (Mirror Image of Itself)?

A binary tree is a data structure tree that consists of connected nodes, each node has at most two children that are linked exactly with one edge. In this tutorial, we’ll show how to check if a binary tree is symmetric. We will write a function that returns true if the tree is mirror of itself, else false. For example, the following binary tree is symmetric, our function should return true in this case:

The following binary tree is not symmetric, although the two subtrees have the same tree structure:

We are going to write a recursive function that takes two trees as input parameters and returns true if trees are mirror and false if trees are not mirrored. It will recursively checks the two roots and subtrees under the root. The following conditions will be applied:

• The two root nodes have the same value
• The left subtree of one root node is a mirror reflection of the right subtree of the other root node

Below is the implementation of the above algorithm.

// C# program to check if binary tree is symmetric or not (mirror of itself)
using System;

class Program
{
    static async Task Main(string[] args)
    {
        BinaryTree tree = new BinaryTree();
        int[] arr = { 1, 2, 2, 3, 4, 4, 3 };
        tree.root = tree.PopulateTree(arr, 0);
        bool output = tree.isSymmetric();
        if (output == true)
            Console.WriteLine("Tree Is Symmetric");
        else
            Console.WriteLine("Tree Is Not symmetric");
    }
}

class Node
{
    public int key;
    public Node left, right;

    public Node(int data)
    {
        key = data;
        left = right = null;
    }
}

class BinaryTree
{
    public Node root;

    // Function to populate the binary tree from an array
    public Node PopulateTree(int[] arr, int i)
    {
        Node root = null;
        // Base case for recursion
        if (i < arr.Length)
        {
            root = new Node(arr[i]);

            // insert left child
            root.left = PopulateTree(arr, 2 * i + 1);

            // insert right child
            root.right = PopulateTree(arr, 2 * i + 2);
        }
        return root;
    }

    // Returns true if trees with roots as root1 and root2 are mirror
    bool isMirror(Node node1, Node node2)
    {
        // if both nodes are empty, then they are mirror image
        if (node1 == null && node2 == null)
            return true;

        // For two trees to be mirror images, the following three conditions must be true
        // 1 - Their root node's key must be same
        // 2 - left subtree of left tree and right subtree of right tree have to be mirror images
        // 3 - right subtree of left tree and left subtree of right tree have to be mirror images
        if (node1 != null && node2 != null
            && node1.key == node2.key)
            return (isMirror(node1.left, node2.right)
                    && isMirror(node1.right, node2.left));

        // if none of the above conditions
        // is true then root1 and root2 are
        // mirror images
        return false;
    }

    // returns true if the tree is symmetric
    // i.e mirror image of itself
    public bool isSymmetric()
    {
        // check if tree is mirror of itself
        return isMirror(root, root);
    }
}

In this tutorial, we implemented a recursive function to check if a binary tree is symmetric or not. Do you have better solution? Please share it in the comments.