Symmetric Tree

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:

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

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

Solution: Using recursion

Two trees are a mirror reflection of each other if:

• Their two roots have the same value.
• The right subtree of each tree is a mirror reflection of the left subtree of the other tree.

bool isSymmetricUtil(TreeNode *left, TreeNode *right) {
    if (!left && !right) return true;
    if (!left || !right) return false;
    return left->val == right->val && isSymmetricUtil(left->right, right->left) && isSymmetricUtil(left->left, right->right);
}

bool isSymmetric(TreeNode* root) {
    return isSymmetricUtil(root, root);
}

Solution: Using Iterative

We push two roots onto the stack each time. And we first check if two roots are the same Then we push left child and right child, right child and left child of the two roots onto the stack.

bool isSymmetric(TreeNode* root) {
    queue<TreeNode*> q;
    q.push(root);
    q.push(root);

    while (!q.empty()) {
        TreeNode *t1 = q.front();
        q.pop();
        TreeNode *t2 = q.front();
        q.pop();

        if (t1 == NULL && t2 == NULL) continue;
        if (t1 == NULL || t2 == NULL) return false;
        if (t1->val != t2->val) return false;

        q.push(t1->left);
        q.push(t2->right);

        q.push(t1->right);
        q.push(t2->left);
    }
    return true;
}

Solution: Using level order traversal

bool isSymmetricUtil(vector<TreeNode *> level) {
    for (int i=0, j=level.size()-1; i<j; i++, j--) {
        if (!level[i] && !level[j]) continue;

        if (!level[i] && level[j]) return false;
        else if (level[i] && !level[j]) return false;
        else if (level[i]->val != level[j]->val) return false;
    }
    return true;
}

bool isSymmetric(TreeNode* root) {
    if (!root) return true;

    queue<TreeNode *> q;
    q.push(root);
    while (true) {
        int size = q.size();
        if (size == 0) break;

        vector<TreeNode *> level;
        while (size) {
            TreeNode *node = q.front();
            q.pop();
            level.push_back(node);

            if (node) {
                q.push(node->left);
                q.push(node->right);                                        
            }
            size -= 1;
        }

        if (!isSymmetricUtil(level)) return false;
    }
    return true;
}