0101.md

101. Symmetric Tree

Level:

Topic:

Similar Problem:

• 100. Same Tree

Question

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

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

Intuition

Recursive & Iterative

Check if root is null, then compare two subtrees

• if both is null, it's symmetric
• if either is null, it's not symmetric
• if the value is differ, it's not symmetric
• recursive calls on one's left and the other's right and vice versa

Code

Time: O(n)
Space: O(n)

Iterative

public boolean isSymmetric(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<>();

    q.add(root);
    q.add(root);

    while (!q.isEmpty()) {
        TreeNode left = q.poll();
        TreeNode right = q.poll();

        if (left == null && right == null)
            continue;

        if (left == null || right == null)
            return false;

        if (left.val != right.val)
            return false;

        q.add(left.left);
        q.add(right.right);

        q.add(left.right);
        q.add(right.left);
    }

    return true;
}

Recursive

public boolean isSymmetric(TreeNode root) {
    if (root == null)
        return true;
    return helper(root.left, root.right);
}

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