Tree Symmetry and Comparison

Place a mirror at the center of a perfectly symmetrical face, and the reflection should match the original. Trees can exhibit the same property — a structure that looks identical when flipped around its center line.

But symmetry is just one form of structural comparison. We might also ask:

• Are two trees identical (exact copies)?
• Is one tree a subtree of another?
• Are two trees structurally isomorphic (same shape, different values)?

These questions arise constantly in real systems: comparing ASTs for code deduplication, validating DOM structures, testing configuration equivalence, or detecting code cloning patterns. Mastering tree comparison patterns gives you tools applicable far beyond standard algorithm problems.

Tree comparison problems come in several flavors, each with different computational complexity and algorithmic approaches:

1. Symmetry (Self-Comparison): Is a tree a mirror image of itself around its root? The left subtree should be a mirror of the right subtree.

2. Equality (Same Tree): Are two trees structurally identical with the same values at each position? Every node must match exactly.

3. Subtree Matching: Is one tree contained within another as a subtree? One tree must appear exactly as a subtree rooted at some node of the other.

4. Structural Isomorphism: Do two trees have the same shape regardless of values? We care about structure, not content.

5. Flip Equivalence: Can we make two trees identical by flipping (swapping left and right children) at any nodes?

A tree is symmetric if it's a mirror image of itself around its center. Formally, the left subtree is a mirror reflection of the right subtree.

What does 'mirror' mean?

Two trees T1 and T2 are mirrors if:

1. Their roots have the same value
2. T1's left subtree is a mirror of T2's right subtree
3. T1's right subtree is a mirror of T2's left subtree

Example:

    Symmetric:              Not Symmetric:
        1                       1
       / \                     / 
      2   2                   2   2
     / \ / \                   \   
    3  4 4  3                   3   3

In the symmetric tree, we can fold it along the center, and left matches right. In the non-symmetric tree, the 3s are both on the right side of their parents.

Visualizing the Comparison:

For the symmetric tree:

        1
       / 
      2   2
     / \ / 
    3  4 4  3

The isMirror checks compare:

• 2 (left) with 2 (right) ✓
• 3 (left.left) with 3 (right.right) ✓ [outer edges]
• 4 (left.right) with 4 (right.left) ✓ [inner edges]

The Cross-Comparison Pattern:

The crux of the algorithm is the cross-comparison: we compare t1.left with t2.right (outer) and t1.right with t2.left (inner). This captures the mirror flipping — what's on the left in one tree should match what's on the right in the other.

Two trees are identical if they have the same structure and every corresponding node has the same value. This is the most straightforward comparison: march through both trees simultaneously and verify every node matches.

The Simultaneous Recursion Pattern:

We traverse both trees in lockstep:

• If both current nodes are null → match (empty subtrees are equal)
• If one is null and the other isn't → not equal (structure differs)
• If values differ → not equal
• Recursively: both left subtrees equal AND both right subtrees equal

Comparison: Same Tree vs Symmetric:

The implementation difference is just one word: which child pairs are compared recursively.

Why Short-Circuiting Matters:

Notice the use of && (logical AND). In most languages, && short-circuits: if p.val !== q.val, we don't even evaluate the recursive calls. This provides early termination when trees differ, potentially saving significant computation.

Alternative: Using OR for Short-Circuit Failure:

// Equivalent with explicit early return
if (p.val !== q.val) return false;
if (!isSameTree(p.left, q.left)) return false;
return isSameTree(p.right, q.right);

Both approaches work; the single-line version is more concise, while explicit returns can be clearer for debugging.

The Subtree of Another Tree problem asks: is tree subRoot a subtree of tree root? A subtree must include all descendants — you can't take just part of a branch.

Key Insight:

subRoot is a subtree of root if and only if there exists some node N in root such that the tree rooted at N is identical to subRoot.

So we reduce subtree matching to:

1. Find all potential match points (nodes with same value as subRoot.val)
2. At each match point, check if subtrees are identical

The Naive Approach:

At every node of root, check if the subtree rooted there equals subRoot. This gives O(n × m) time where n is size of root, m is size of subRoot.

Optimized Approach — Tree Serialization:

We can achieve O(n + m) time by serializing trees to strings and using string matching (like KMP or Rabin-Karp):

1. Serialize both trees using preorder traversal with null markers
2. Check if serialized subRoot is a substring of serialized root

Why null markers are critical:

   Tree 1:      Tree 2:
     1            1
    /            / 
   1            1   null

Without null markers, both serialize to "1,1" — but they're different trees! With null markers: "1,1,null,null" vs "1,1,null,null,null" — correctly different.

function serialize(node: TreeNode | null): string {
    if (node === null) return "#";  // Null marker
    return `${node.val},${serialize(node.left)},${serialize(node.right)}`;
}

function isSubtreeOptimal(root: TreeNode, subRoot: TreeNode): boolean {
    const rootSerialized = serialize(root);
    const subSerialized = serialize(subRoot);
    return rootSerialized.includes(subSerialized);  // O(n+m) with good impl
}

While not strictly a comparison problem, Invert Binary Tree is closely related. Inverting creates a mirror image, turning the tree into what the symmetric check would compare against.

The relationship:

• A tree is symmetric iff it equals its own inverse
• Inverting twice returns the original tree
• Inverting is to trees what reversing is to arrays

The algorithm is elegantly simple:

1. Swap the left and right children
2. Recursively invert the left subtree
3. Recursively invert the right subtree

Connection to Symmetry:

We can now express symmetry in terms of inversion:

// A tree is symmetric iff it equals its inverse
function isSymmetricViaInversion(root: TreeNode | null): boolean {
    // Create a copy of the tree (don't modify original)
    const copy = cloneTree(root);
    const inverted = invertTree(copy);
    return isSameTree(root, inverted);
}

This is O(n) time but O(n) extra space for the copy. The direct symmetric check is more efficient (no copy needed), but this formulation provides deeper insight into what symmetry means.

Two trees are flip equivalent if we can make them identical by flipping (swapping left and right children) at any nodes. This is a more relaxed form of equality — structure can be rearranged, but the tree's 'content' is the same.

Intuition:

Imagine the tree is made of hinges. At each node, you can swing the children to swap their positions. Two trees are flip equivalent if any sequence of swings can make them match.

Key Insight:

At each pair of corresponding nodes, either:

• The children match directly (no flip needed), OR
• The children match crossed (flip at this node)

We just need to check if EITHER arrangement works at each level.

Visualizing Flip Equivalence:

   Tree 1:          Tree 2:
       1               1
      / \             / 
     2   3           3   2
    /     \             / 
   4       5           5   4

These are flip equivalent:

• Flip at root: 2↔3 swap
• Flip at node 2: now 4 is on different side
• Flip at node 3: now 5 matches

Complexity Analysis:

At each node pair, we might check both arrangements, but this doesn't blow up to exponential because:

1. If we find a mismatch early, we prune
2. Each actual node pair is checked at most twice (once for each possible parent flip)

The overall time remains O(n), though with a larger constant factor than simple equality.

Tree comparison algorithms appear throughout software engineering, often in unexpected places.

1. React's Reconciliation Algorithm:

React maintains a virtual DOM tree. When state changes, it computes a new tree and compares it to the old one using a tree diff algorithm. Understanding tree comparison helps you understand React's performance characteristics and when to use keys.

2. Code Duplication Detection:

Compilers and code analysis tools parse source code into Abstract Syntax Trees (ASTs). Subtree matching identifies cloned code blocks, enabling refactoring suggestions and plagiarism detection.

3. Merge Conflict Detection:

Version control systems represent file changes as trees. Detecting conflicting changes involves comparing tree structures and finding where modifications overlap.

4. Configuration Validation:

JSON/XML configurations are tree-structured. Validating that a configuration matches a schema is a tree comparison problem.