417. Check if Two Binary Trees Are Mirrors of Each Other

Given two binary trees (each in level-order token format, one per line), print 'Yes' if the second is the mirror image of the first - meaning swapping every node's left and right child in one tree would produce the other - otherwise print 'No'. The tree is given as space-separated level-order tokens, where 'N' means no node there: the first token is the root, then for each node dequeued in level order you read its left-child token then its right-child token (if input runs out early, remaining children are treated as N).

Input: Two lines, each containing space-separated level-order tokens ('N' marks an absent child) for one of the two trees. Output: Print 'Yes' if the second tree is the mirror image of the first, otherwise print 'No'.

1 <= number of nodes in each tree <= 10^5

Two nodes that are BOTH absent count as a valid match (mirrors of nothing is still nothing) - but one being absent while the other is present is always a mismatch, an easy edge case to overlook.

Given two separate binary trees, check whether one is exactly the mirror image of the other. Brute force: Compare the two trees for plain structural EQUALITY (left-to-left, right-to-right) - this checks if they're IDENTICAL, not if they're mirrors of each other, which is a different (and wrong, for this problem) comparison. Optimised: Crossing the comparison (tree1's left against tree2's right, and vice versa) directly encodes the mirror relationship between two SEPARATE trees - this is the exact same cross-comparison technique used for checking if a SINGLE tree is symmetric, just applied between two distinct trees instead of one tree's two halves.

Use a single queue holding pairs of nodes to compare, starting with (tree1's root, tree2's root). At each step, dequeue a pair, check their values match, then enqueue (tree1 node's left, tree2 node's right) and (tree1 node's right, tree2 node's left) if both exist. This checks the same mirror condition without any recursion at all, which matters because the trees can have up to 1e5 nodes and a skewed (very deep) tree could blow the recursion stack in the recursive version; the iterative queue's memory usage is bounded by the traversal's width rather than the tree's depth. Time: O(n) Space: O(w), bounded by the widest level of the tree

Instead of materializing a mirrored copy, recursively compare the two trees directly: check that tree1's root value equals tree2's root value, then recursively verify that tree1's left subtree mirrors tree2's right subtree, and tree1's right subtree mirrors tree2's left subtree. This checks exactly the same mirror condition as the brute-force approach but without ever constructing an intermediate tree, only using recursion-stack space proportional to the tree's height rather than an entire extra copy of all n nodes. Time: O(n) Space: O(h) recursion stack, where h is tree height

Recursively build a brand-new tree that is the mirror image of the first tree by swapping left and right children at every node as you copy it. Then perform a separate structural equality check, comparing this newly built mirrored tree against the second tree node by node. This correctly tests the mirror relationship, but it wastes an entire extra O(n) traversal and O(n) memory allocating a full copy of the tree that is only used once for comparison and then discarded. Time: O(n) Space: O(n) for the extra mirrored tree

1. Recursively compare the two trees: the CURRENT pair of nodes must have equal values (or both be absent). 2. The first tree's LEFT subtree must mirror-match the second tree's RIGHT subtree. 3. The first tree's RIGHT subtree must mirror-match the second tree's LEFT subtree.

Time: O(n) - assuming both trees have a similar number of nodes, every node pair is compared exactly once. Space: O(h) for the recursion stack.

Test with both trees being single nodes, trees with differing shapes (immediate 'No'), and trees with up to 10^5 nodes each for performance.

Be ready to connect this directly to the 'is this single tree symmetric' problem - recognizing that checking mirror-ness between two trees and checking symmetry within one tree use the identical cross-comparison recursion is a great pattern-matching signal.