Check if 2 trees are mirror or not

The problem, simply

You get two binary trees, A and B. Say true if B is what you see when you hold A up to a mirror, and false otherwise.

In a mirror, left and right swap. So the roots must hold the same value, A's left side must be the mirror of B's right side, and A's right side must be the mirror of B's left side. Missing children must be missing on the matching side too.

A story to remember it

Picture it

Examples

Way 1: the simple way

Build the mirror of A yourself by swapping left and right at every node into a new tree. Then check if that new tree is equal to B, node by node.

1. mirror(node): make a copy whose left is mirror(node.right) and whose right is mirror(node.left).
2. same(x, y): both null is true, one null is false, else values equal and same(x.left, y.left) and same(x.right, y.right).
3. Return same(mirror(A), B).

class Solution {
    public boolean areMirror(TreeNode a, TreeNode b) {
        return same(mirror(a), b);
    }

    private TreeNode mirror(TreeNode n) {
        if (n == null) return null;
        TreeNode copy = new TreeNode(n.val);
        copy.left = mirror(n.right);   // swap sides while copying
        copy.right = mirror(n.left);
        return copy;
    }

    private boolean same(TreeNode x, TreeNode y) {
        if (x == null && y == null) return true;
        if (x == null || y == null) return false;
        return x.val == y.val && same(x.left, y.left) && same(x.right, y.right);
    }
}

How long it takes: one walk to copy, one walk to compare, O(n). Extra room: a whole new tree, O(n).

Way 2: the clever way

Skip the copy. Walk both trees at the same time and compare crossed pairs directly.

1. If both nodes are null, this pair is fine.
2. If only one is null, it is not a mirror.
3. The values must be equal.
4. Check A's left with B's right, and A's right with B's left.

class Solution {
    public boolean areMirror(TreeNode a, TreeNode b) {
        if (a == null && b == null) return true;     // both missing: fine
        if (a == null || b == null) return false;    // only one missing
        return a.val == b.val
            && areMirror(a.left, b.right)            // cross: left with right
            && areMirror(a.right, b.left);           // cross: right with left
    }
}

How long it takes: each pair is checked once and we stop at the first mismatch, O(n). Extra room: only the waiting helpers, as many as the tree is tall, O(h).

Watch out for

• Checking only values, not shapes. A child missing on one side must be missing on the matching side too. The two null checks handle this.
• Writing a == null || b == null before a == null && b == null. Then two empty trees return false.
• Different sizes. Mirrors always have the same number of nodes, so a size check is a quick early false, but the main walk already catches it.

What interviewers ask next

• Is one tree symmetric (a mirror of itself)? Call areMirror(root.left, root.right). That is LeetCode 101.
• Without recursion? Put the pair (a, b) in a queue. Each step, take a pair, check it, then add (a.left, b.right) and (a.right, b.left).
• Turn a tree into its mirror in place? Swap left and right at every node with any walk. That is LeetCode 226, Invert Binary Tree.
• What if the trees are n-ary (any number of children)? Compare child i of A with child k - 1 - i of B.

Remember this

Grown-up words: the dancing pairs are the recursive mirror check; the pairs waiting their turn are the call stack, which is O(h) deep, where h is the height of the tree.