426. Tree Isomorphism Problem

Given two binary trees (each in level-order token format, one per line), print 'Yes' if they are isomorphic - meaning one can be transformed into the other by swapping the left and right children of any number of nodes (zero or more, at any positions) - otherwise print 'No'.

Input: Two lines, each a space-separated level-order token representation ('N' for missing children) of a binary tree - one tree per line. Output: Print 'Yes' if the two trees are isomorphic, otherwise print 'No'.

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

Two IDENTICAL trees are trivially isomorphic (zero swaps needed anywhere), and a full MIRROR image is also isomorphic (every node happens to need a swap) - isomorphism is a broader, more flexible notion encompassing both of these as special cases.

Check whether two binary trees can be made identical to each other by swapping the left/right children of some (possibly zero) nodes in one of them. Brute force: Try every possible combination of which nodes to swap in one of the trees and check for exact equality afterward - this is exponential in the number of nodes, completely impractical. Optimised: Checking BOTH possibilities (unswapped match, OR swapped match) at every single node recursively, independently at each level, correctly explores all combinations of swaps WITHOUT ever needing to enumerate them explicitly - each node's swap decision only affects the local comparison, not any global choice that needs to be tracked.

Compare the two trees directly with a single recursive function: two nodes are isomorphic-matching if both are null, or both exist with equal values and either (their left children match each other and their right children match each other) or (one tree's left matches the other's right and vice versa). This checks both the 'no swap' and 'swap' possibility at every node on the fly without ever constructing any canonical string representation, so each node is visited a constant number of times overall, giving a clean linear-time algorithm that also uses far less memory than building explicit serialized strings. Time: O(n) Space: O(h)

For each tree, explicitly enumerate every possible way of swapping left/right children at each internal node (2 choices per node, so 2^k combinations for k internal nodes), serialize each resulting tree shape/value arrangement into a string, and collect the lexicographically smallest such string as that tree's canonical signature; then compare the two trees' canonical signatures for equality. This is correct by definition of isomorphism but the number of swap combinations to try grows exponentially with the number of internal nodes. Time: O(2^n * n) Space: O(n)

Recursively build a single canonical string representation of each tree bottom-up: at each node, first canonicalize its left and right subtrees, then always output the two child representations in a fixed, consistent order (for example, whichever child's string is lexicographically smaller comes first), regardless of which side they were originally on. Comparing the two trees' single resulting canonical strings for exact equality then correctly answers whether they're isomorphic. This avoids ever trying multiple swap combinations explicitly, but comparing and ordering subtree strings at every one of the n nodes can cost up to O(n) per comparison in the worst case, giving quadratic behavior on deep trees. Time: O(n^2) Space: O(n)

1. Recursively compare the two trees: their root values must match. 2. Then check EITHER of two possibilities: (both trees' left subtrees are isomorphic to each other AND both right subtrees are isomorphic to each other), OR (the first tree's left is isomorphic to the second tree's right, AND the first tree's right is isomorphic to the second tree's left). 3. If either possibility holds at every level, the trees are isomorphic.

Time: O(n) in the typical case - though technically the recursive branching (checking two possibilities per node) could in principle explore more paths, in practice this resolves in linear time since a match at one level doesn't require re-checking already-matched substructures. Space: O(h) for the recursion stack.

Test two identical trees, two trees that are exact mirrors of each other, trees with the same node count but a shape no swap sequence can reconcile, and up to 10^5 nodes per tree for performance.

Be ready to explain that unlike checking if two trees are simply 'mirror images' (which requires EVERY node to be swapped, a single global choice), isomorphism allows swaps to be decided INDEPENDENTLY at each node - a subtle but important distinction.