121. Check if a Binary Tree Is Symmetric

Given a binary tree, print 'Yes' if it is a mirror of itself around its center (symmetric), 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: A single line of space-separated level-order tokens describing the binary tree ('N' marks an absent child). Output: Print 'Yes' if the tree is symmetric around its center, otherwise print 'No'.

1 <= number of nodes <= 10^5

A single node with no children is trivially symmetric - useful as a base case and a quick sanity check before trusting more complex logic.

Check whether a binary tree looks the same as its own mirror image, folded around its center. Brute force: Directly compare the left and right subtrees for plain EQUALITY (not mirroring) - this is WRONG, since a symmetric tree's two sides are mirror images of each other, not identical copies (e.g. one side's left-right order is reversed relative to the other). Optimised: Recursively comparing 'left's left against right's right' and 'left's right against right's left' (rather than 'left against right' directly) correctly captures the mirror relationship - a single recursive pass checking both cross-pairs at every level verifies symmetry throughout the whole tree.

Instead of building a mirrored copy, recursively compare the left and right subtrees of the root directly against each other in mirrored fashion: check that left.value equals right.value, then recursively compare left.left with right.right and left.right with right.left. This produces exactly the same verdict as comparing against a built mirror tree, but since no second tree is ever constructed, the extra space drops from linear in the number of nodes down to just the recursion depth. Time: O(n) Space: O(h)

Use an explicit queue and push the root's left and right children onto it as a pair; then repeatedly pop two nodes at a time, check they have equal values (or are both null), and push their children in mirrored order (first's left with second's right, first's right with second's left) back onto the queue. This computes the same result as the recursive comparison but does so iteratively, which avoids relying on the call stack entirely, and with the tree allowed to have up to 10^5 nodes a skewed tree could otherwise cause a recursive solution's stack depth to reach 10^5 and risk a stack overflow, making the iterative version the more robust choice at this scale. Time: O(n) Space: O(n)

Build a full mirrored copy of the tree by recursively swapping every node's left and right children, then compare this mirrored copy against the original tree node by node for structural and value equality. This is correct because a tree is symmetric exactly when it equals its own mirror image, but allocating an entire second tree just to compare against wastes memory that is not really needed. Time: O(n) Space: O(n)

1. Compare the tree's left subtree and right subtree as MIRROR images of each other, not as identical copies. 2. Their root values must match; the left subtree's LEFT child must mirror the right subtree's RIGHT child, and the left subtree's RIGHT child must mirror the right subtree's LEFT child. 3. Recurse this cross-comparison down both sides simultaneously.

Time: O(n) - every node pair is compared exactly once. Space: O(h) for the recursion stack.

Test with a single-node tree (trivially symmetric), a tree whose two sides have matching values but different shapes (expect 'No'), and a tree with 10^5 nodes for performance.

Be ready to clarify the difference between 'symmetric' (mirrors itself) and simply 'checking if two trees are IDENTICAL' - a common mix-up, since the comparison logic for symmetry crosses left/right in a specific way that identical-tree comparison does not.