Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

But the following [1,2,2,null,3,null,3] is not:

Note: Bonus points if you could solve it both recursively and iteratively.

Recursive

A tree is symmetric if the two subtrees beneath any root has:

1. the left and right child has the same value
2. The left child’s left matches with right child’s right
3. The left child’s right matches with left child’s left.

The base case is when two leaf level node matches and they don’t have children.

    bool isSymmetric(TreeNode* root) {
        return isSym(root, root);
    }
    bool isSym(TreeNode* leftNode, TreeNode* rightNode){
        if(leftNode == NULL && rightNode != NULL) return false;
        if (leftNode != NULL && rightNode == NULL)return false;
        if(leftNode == NULL && rightNode == NULL) return true;
        return (leftNode -> val == rightNode -> val &&
            isSym(leftNode -> left, rightNode -> right) && 
            isSym(leftNode -> right , rightNode -> left));
    }

Improvement

In the previous code, we have three coditions to check, but observe that it only wants to know if both nodes are null or just one is null so we can do

if(leftNode == NULL && rightNode == NULL) return true;
if(left == NULL || right == NULL) return falase;

ITerative

    bool isSymmetric(TreeNode* root) {
        stack<TreeNode*> s;
        s.push(root);
        s.push(root);
        while(!s.empty()){
            TreeNode* leftNode = s.top();
            s.pop();
            TreeNode* rightNode = s.top();
            s.pop();
            if(leftNode == NULL && rightNode == NULL) continue;
            if(leftNode == NULL || rightNode == NULL) return false;
            if(leftNode -> val == rightNode -> val){
                s.push(leftNode -> left);
                s.push(rightNode -> right);
                s.push(leftNode -> right);
                s.push(rightNode -> left);
            }
            else
                return false;
        }
        return true;
    }