Symmetric Tree

Problem

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

Solution

Recursive Solution Using helper() method

public class Solution {

    public boolean isSymmetric(TreeNode root) {
        return helper(root, root);
    }

    private boolean helper(TreeNode node1, node2) {
        if (node1 == null && node2 == null) return true;
        if (node1 == null || node2 == null) return false;
        return node1.val == node2.val && helper(node1.left, node2.right) && helper(node1.right, node2.left);
    }
}

Iterative Solution Using Queue

public class Solution {
    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode node1 = q.poll(), node2 = q.poll();
            if (node1 == null && node2 == null) continue;
            if (node1 == null || node2 == null) return false;
            if (node1.val != node2.val) return false;
            q.offer(node1.left);
            q.offer(node2.right);
            q.offer(node1.right);
            q.offer(node2.left);
        }
        return true;
    }
}

Analysis

This problem becomes easier when we solve it using Divide & Conquer
To check if the given tree is symmetric, we need to see if each subtree is symmetric
Then the problem becomes check if the corresponding subtrees are symmetric
The correct set of subtree should be node1.left & node1.right and node1.right & node2.left
If all node1 and node2 are symmetric, then we know the entire given tree is also symmetric