3.Symmetric Tree

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2:

Input: root = [1,2,2,null,3,null,3]
Output: false

Iterative Solution using Queue

Note:- Level order traversal of a Symmetric binary tree is palindromic.

class Solution
{
public:
    bool isSymmetric(TreeNode *root)
    {

        if (root == NULL)
        {
            return true;
        }

        if (!root->left && !root->right)
        {
            return true;
        }
        else if (!root->left || !root->right)
        {
            return false;
        }

        bool res = true;
        queue<TreeNode *> q;
        q.push(root->left);
        q.push(root->right);

        while (!q.empty())
        {

            TreeNode *leftNode = q.front();
            q.pop();
            TreeNode *rightNode = q.front();
            q.pop();

            if (leftNode->val != rightNode->val)
            {
                res = false;
                break;
            }

            if (leftNode->left && rightNode->right)
            {
                q.push(leftNode->left);
                q.push(rightNode->right);
            }
            else if (leftNode->left || rightNode->right)
            {
                res = false;
                break;
            }

            if (leftNode->right && rightNode->left)
            {
                q.push(leftNode->right);
                q.push(rightNode->left);
            }
            else if (leftNode->right || rightNode->left)
            {
                res = false;
                break;
            }
        }

        return res;
    }
};

Solution: (Recursion)

class Solution
{
public:
    bool check(TreeNode *leftT, TreeNode *rightT)
    {
        if (!leftT && !rightT)
        {
            return true;
        }

        if ((leftT && !rightT) || (rightT && !leftT))
        {
            return false;
        }

        if (leftT->val != rightT->val)
        {
            return false;
        }

        if (!check(leftT->left, rightT->right))
        {
            return false;
        }

        if (!check(leftT->right, rightT->left))
        {
            return false;
        }

        return true;
    }

    bool isSymmetric(TreeNode *root)
    {
        if (!root->left && !root->right)
        {
            return true;
        }

        if (!check(root->left, root->right))
        {
            return false;
        }

        return true;
    }
};