Common Tree Patterns - Learning Module

Loading content...

0/276

Tree Symmetry and Comparison

Mirrors and Clones — Analyzing Tree Structure

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.

What You Will Master

By the end of this page, you will:

• Understand the different types of tree structural comparison • Implement elegant recursive solutions for symmetry detection • Solve tree equality and subtree matching problems • Recognize the deep connection between simultaneous recursion and tree comparison • Apply serialization techniques for advanced matching • Handle edge cases with precision (nulls, different sizes, different structures)

Types of Tree Comparison

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?

Tree Comparison Problem Types
Problem Type	Compares	Key Insight	Complexity
Symmetry	Left vs Right (mirror)	Compare left with right's mirror	O(n)
Equality	Tree vs Tree (exact)	Simultaneous DFS on both trees	O(min(n,m))
Subtree Match	Small in Large	Check equality at each node	O(n × m) naive, O(n+m) optimal
Isomorphism	Shape only	Ignore values, compare structure	O(min(n,m))
Flip Equivalence	With swaps allowed	Check both orderings at each node	O(n)

The Common Pattern

All tree comparison problems share a core pattern: simultaneous recursion on two tree positions. We compare corresponding nodes and recursively verify that subtrees satisfy the desired relationship. The variations differ in what 'corresponding' means and what conditions we check.

Symmetric Tree — The Mirror Property

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:

Their roots have the same value
T1's left subtree is a mirror of T2's right subtree
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
interface TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
}
 
/**
 * Determines if a binary tree is symmetric (a mirror of itself).
 * 
 * Key insight: Checking symmetry is checking if left and right
 * subtrees are mirrors of each other.
 * 
 * Time: O(n) - visit each node once
 * Space: O(h) - recursion depth equals tree height
 */
function isSymmetric(root: TreeNode | null): boolean {
    // Empty tree or single node is symmetric
    if (root === null) {
        return true;
    }
    
    // Check if left and right subtrees are mirrors
    return isMirror(root.left, root.right);
}
 
/**
 * Determines if two trees are mirror images of each other.
 * 
 * Mirror relationship:
 * - Both null: mirrors (base case)
 * - One null: not mirrors
 * - Different values: not mirrors
 * - Recursively: t1.left mirrors t2.right AND t1.right mirrors t2.left
 */
function isMirror(t1: TreeNode | null, t2: TreeNode | null): boolean {
    // Base case 1: Both null - they're mirrors
    if (t1 === null && t2 === null) {
        return true;
    }
    
    // Base case 2: One null, one not - not mirrors
    if (t1 === null || t2 === null) {
        return false;
    }
    
    // Base case 3: Values differ - not mirrors
    if (t1.val !== t2.val) {
        return false;
    }
    
    // Recursive case: Check cross-children
    // Left's left with Right's right (outer edges)
    // Left's right with Right's left (inner edges)
    return isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
}

Visualizing the Comparison:

For the symmetric tree:

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.

Iterative Alternative

Symmetry can also be checked iteratively using a queue. Push pairs to compare: (left.left, right.right) and (left.right, right.left). This is BFS-style and avoids recursion stack limits for very deep trees. Both approaches are O(n) time.

Same Tree — Exact Equality

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Determines if two binary trees are exactly identical.
 * 
 * Two trees are identical iff:
 * - Both are null, OR
 * - Both have the same root value AND
 *   left subtrees are identical AND
 *   right subtrees are identical
 * 
 * Time: O(min(n, m)) - stop early if mismatch found
 * Space: O(min(h1, h2)) - recursion depth
 */
function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
    // Both null - equal (base case 1)
    if (p === null && q === null) {
        return true;
    }
    
    // One null, other not - not equal (base case 2)
    if (p === null || q === null) {
        return false;
    }
    
    // Check current node and recursively check subtrees
    return p.val === q.val && 
           isSameTree(p.left, q.left) && 
           isSameTree(p.right, q.right);
}

Comparison: Same Tree vs Symmetric:

Aspect	Same Tree	Symmetric
What's compared	p.left with q.left	p.left with q.right (mirror)
Relationship	Direct correspondence	Mirror correspondence
Base condition	Both structures identical	One structure is other's reflection

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.

Subtree Matching — Finding Trees Within Trees

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:

Find all potential match points (nodes with same value as subRoot.val)
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Determines if subRoot is a subtree of root.
 * 
 * Strategy: At each node of root, check if its subtree matches subRoot.
 * 
 * Time: O(n × m) - for each of n nodes, potentially compare m nodes
 * Space: O(h_root + h_sub) - recursion stacks
 * 
 * Note: Can be optimized to O(n + m) using tree serialization or hashing.
 */
function isSubtree(root: TreeNode | null, subRoot: TreeNode | null): boolean {
    // Null subRoot is subtree of anything (empty tree is everywhere)
    if (subRoot === null) {
        return true;
    }
    
    // Null root but non-null subRoot - can't be a subtree
    if (root === null) {
        return false;
    }
    
    // Check if trees match at current position
    if (isSameTree(root, subRoot)) {
        return true;
    }
    
    // Otherwise, check if subRoot appears in either subtree
    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
 
/**
 * Helper: Check if two trees are identical (from previous section)
 */
function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
    if (p === null && q === null) return true;
    if (p === null || q === null) return false;
    return p.val === q.val && 
           isSameTree(p.left, q.left) && 
           isSameTree(p.right, q.right);
}

Subtle Definition

A node's subtree includes ALL its descendants, not just a prefix. If subRoot has nodes A→B→C, finding A→B in root is NOT enough — we need the complete structure including C. This is why we use equality check, not just prefix matching.

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):

Serialize both trees using preorder traversal with null markers
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
}

Invert Binary Tree — The Transformation View

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:

Swap the left and right children
Recursively invert the left subtree
Recursively invert the right subtree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Inverts a binary tree — creates its mirror image.
 * 
 * This is the transformation that symmetry compares against.
 * Inverting twice returns the original tree.
 * 
 * Time: O(n) - visit each node once
 * Space: O(h) - recursion depth
 */
function invertTree(root: TreeNode | null): TreeNode | null {
    // Base case: null tree inverts to null
    if (root === null) {
        return null;
    }
    
    // Recursively invert subtrees
    const invertedLeft = invertTree(root.left);
    const invertedRight = invertTree(root.right);
    
    // Swap children
    root.left = invertedRight;
    root.right = invertedLeft;
    
    return root;
}
 
/**
 * Alternative: Swap first, then recurse (also correct)
 */
function invertTreeSwapFirst(root: TreeNode | null): TreeNode | null {
    if (root === null) return null;
    
    // Swap first
    [root.left, root.right] = [root.right, root.left];
    
    // Recurse on new positions
    invertTree(root.left);
    invertTree(root.right);
    
    return root;
}

The Famous Tweet

This problem became famous when a Google engineer tweeted that he couldn't invert a binary tree on a whiteboard. It's now a touchstone example — a simple problem that tests whether you understand recursion on trees. Don't let its simplicity fool you; understanding WHY it works is more important than remembering HOW.

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.

Flip Equivalent Trees — Generalized Comparison

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Determines if two trees are flip equivalent — can be made identical
 * by swapping children at any nodes.
 * 
 * Key insight: At each corresponding pair, check if children match
 * EITHER directly OR crossed (flipped).
 * 
 * Time: O(n) - each node compared at most twice
 * Space: O(h) - recursion depth
 */
function flipEquiv(
    root1: TreeNode | null, 
    root2: TreeNode | null
): boolean {
    // Both null - equivalent
    if (root1 === null && root2 === null) {
        return true;
    }
    
    // One null, other not - not equivalent
    if (root1 === null || root2 === null) {
        return false;
    }
    
    // Values must match at corresponding positions
    if (root1.val !== root2.val) {
        return false;
    }
    
    // Two possibilities:
    // 1. No flip: left matches left, right matches right
    // 2. Flip: left matches right, right matches left
    
    const noFlip = flipEquiv(root1.left, root2.left) && 
                   flipEquiv(root1.right, root2.right);
    
    const withFlip = flipEquiv(root1.left, root2.right) && 
                     flipEquiv(root1.right, root2.left);
    
    return noFlip || withFlip;
}

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:

If we find a mismatch early, we prune
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.

Relationship to Graph Isomorphism

Flip equivalence is a special case of tree isomorphism. For general graphs, isomorphism is much harder (not known to be polynomial time). But for trees, the hierarchical structure allows efficient O(n log n) or even O(n) solutions. Binary trees with flip equivalence are even simpler due to the limited choices at each node.

Practical Applications

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.

Tree Comparison in Software Systems
Application	What's Compared	Algorithm Used	Why It Matters
React Virtual DOM	Old vs New tree	Structural diff	Minimal DOM updates
Git Tree Diff	Commit trees	Recursive comparison	Efficient changesets
Code Clone Detection	AST subtrees	Subtree matching	Find duplicated code
JSON Schema Validation	Instance vs Schema	Structural matching	Config correctness
XML Diff Tools	Document trees	Tree edit distance	Document comparison

Tree Edit Distance

Beyond simple comparison, there's Tree Edit Distance: the minimum number of node insertions, deletions, and relabelings to transform one tree into another. This is more complex (O(n²) to O(n³) depending on variant) but crucial for applications like structured document comparison where 'how different' matters more than 'same or not'.

Summary and Key Takeaways

Tree comparison problems reveal deep patterns in recursive thinking and structural analysis. Let's consolidate what we've learned:

Core Concepts Mastered

•Simultaneous recursion: Compare two tree positions together, recursing in lockstep
•Symmetry = Mirror comparison: Check left against right's reverse (cross-comparison)
•Equality = Direct comparison: Check left against left, right against right
•Subtree matching: Reduce to equality check at each potential root
•Flip equivalence: Allow both direct and crossed child matching at each node
•Serialization optimization: Convert trees to strings for fast pattern matching

The Core Pattern

All comparison problems follow this template:

function compare(t1, t2):
    if both null: return BASE_TRUE
    if one null: return BASE_FALSE
    if values don't match: return false
    return combine(
        compare(t1.left, WHICH_OF_T2),
        compare(t1.right, WHICH_OF_T2)
    )

The variation is in which t2 children we compare against and whether we use AND or OR to combine.

What's Next:

Comparison problems taught us to analyze tree structure. In the next page, we'll tackle the Diameter of a Tree — finding the longest path between any two nodes. This problem combines path computation with whole-tree optimization, introducing the 'return one thing, track another' pattern that appears in many advanced tree algorithms.

Page Complete

You now understand tree comparison at a deep level — from symmetric self-reflection to exact equality to flexible flip equivalence. These patterns form the foundation for understanding how real systems like React's reconciler or Git's tree diff work. The simultaneous recursion pattern transfers to any problem comparing two recursive structures.

Tree Symmetry and Comparison

Mirrors and Clones — Analyzing Tree Structure

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)?

What You Will Master

By the end of this page, you will:

Types of Tree Comparison

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?

Tree Comparison Problem Types
Problem Type	Compares	Key Insight	Complexity
Symmetry	Left vs Right (mirror)	Compare left with right's mirror	O(n)
Equality	Tree vs Tree (exact)	Simultaneous DFS on both trees	O(min(n,m))
Subtree Match	Small in Large	Check equality at each node	O(n × m) naive, O(n+m) optimal
Isomorphism	Shape only	Ignore values, compare structure	O(min(n,m))
Flip Equivalence	With swaps allowed	Check both orderings at each node	O(n)

The Common Pattern

Symmetric Tree — The Mirror Property

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:

Their roots have the same value
T1's left subtree is a mirror of T2's right subtree
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
interface TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
}
 
/**
 * Determines if a binary tree is symmetric (a mirror of itself).
 * 
 * Key insight: Checking symmetry is checking if left and right
 * subtrees are mirrors of each other.
 * 
 * Time: O(n) - visit each node once
 * Space: O(h) - recursion depth equals tree height
 */
function isSymmetric(root: TreeNode | null): boolean {
    // Empty tree or single node is symmetric
    if (root === null) {
        return true;
    }
    
    // Check if left and right subtrees are mirrors
    return isMirror(root.left, root.right);
}
 
/**
 * Determines if two trees are mirror images of each other.
 * 
 * Mirror relationship:
 * - Both null: mirrors (base case)
 * - One null: not mirrors
 * - Different values: not mirrors
 * - Recursively: t1.left mirrors t2.right AND t1.right mirrors t2.left
 */
function isMirror(t1: TreeNode | null, t2: TreeNode | null): boolean {
    // Base case 1: Both null - they're mirrors
    if (t1 === null && t2 === null) {
        return true;
    }
    
    // Base case 2: One null, one not - not mirrors
    if (t1 === null || t2 === null) {
        return false;
    }
    
    // Base case 3: Values differ - not mirrors
    if (t1.val !== t2.val) {
        return false;
    }
    
    // Recursive case: Check cross-children
    // Left's left with Right's right (outer edges)
    // Left's right with Right's left (inner edges)
    return isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
}

Visualizing the Comparison:

For the symmetric tree:

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:

Iterative Alternative

Same Tree — Exact Equality

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Determines if two binary trees are exactly identical.
 * 
 * Two trees are identical iff:
 * - Both are null, OR
 * - Both have the same root value AND
 *   left subtrees are identical AND
 *   right subtrees are identical
 * 
 * Time: O(min(n, m)) - stop early if mismatch found
 * Space: O(min(h1, h2)) - recursion depth
 */
function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
    // Both null - equal (base case 1)
    if (p === null && q === null) {
        return true;
    }
    
    // One null, other not - not equal (base case 2)
    if (p === null || q === null) {
        return false;
    }
    
    // Check current node and recursively check subtrees
    return p.val === q.val && 
           isSameTree(p.left, q.left) && 
           isSameTree(p.right, q.right);
}

Comparison: Same Tree vs Symmetric:

Aspect	Same Tree	Symmetric
What's compared	p.left with q.left	p.left with q.right (mirror)
Relationship	Direct correspondence	Mirror correspondence
Base condition	Both structures identical	One structure is other's reflection

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

Why Short-Circuiting Matters:

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.

Subtree Matching — Finding Trees Within Trees

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:

Find all potential match points (nodes with same value as subRoot.val)
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Determines if subRoot is a subtree of root.
 * 
 * Strategy: At each node of root, check if its subtree matches subRoot.
 * 
 * Time: O(n × m) - for each of n nodes, potentially compare m nodes
 * Space: O(h_root + h_sub) - recursion stacks
 * 
 * Note: Can be optimized to O(n + m) using tree serialization or hashing.
 */
function isSubtree(root: TreeNode | null, subRoot: TreeNode | null): boolean {
    // Null subRoot is subtree of anything (empty tree is everywhere)
    if (subRoot === null) {
        return true;
    }
    
    // Null root but non-null subRoot - can't be a subtree
    if (root === null) {
        return false;
    }
    
    // Check if trees match at current position
    if (isSameTree(root, subRoot)) {
        return true;
    }
    
    // Otherwise, check if subRoot appears in either subtree
    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
 
/**
 * Helper: Check if two trees are identical (from previous section)
 */
function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
    if (p === null && q === null) return true;
    if (p === null || q === null) return false;
    return p.val === q.val && 
           isSameTree(p.left, q.left) && 
           isSameTree(p.right, q.right);
}

Subtle Definition

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):

Serialize both trees using preorder traversal with null markers
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
}

Invert Binary Tree — The Transformation View

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:

Swap the left and right children
Recursively invert the left subtree
Recursively invert the right subtree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Inverts a binary tree — creates its mirror image.
 * 
 * This is the transformation that symmetry compares against.
 * Inverting twice returns the original tree.
 * 
 * Time: O(n) - visit each node once
 * Space: O(h) - recursion depth
 */
function invertTree(root: TreeNode | null): TreeNode | null {
    // Base case: null tree inverts to null
    if (root === null) {
        return null;
    }
    
    // Recursively invert subtrees
    const invertedLeft = invertTree(root.left);
    const invertedRight = invertTree(root.right);
    
    // Swap children
    root.left = invertedRight;
    root.right = invertedLeft;
    
    return root;
}
 
/**
 * Alternative: Swap first, then recurse (also correct)
 */
function invertTreeSwapFirst(root: TreeNode | null): TreeNode | null {
    if (root === null) return null;
    
    // Swap first
    [root.left, root.right] = [root.right, root.left];
    
    // Recurse on new positions
    invertTree(root.left);
    invertTree(root.right);
    
    return root;
}

The Famous Tweet

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.

Flip Equivalent Trees — Generalized Comparison

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Determines if two trees are flip equivalent — can be made identical
 * by swapping children at any nodes.
 * 
 * Key insight: At each corresponding pair, check if children match
 * EITHER directly OR crossed (flipped).
 * 
 * Time: O(n) - each node compared at most twice
 * Space: O(h) - recursion depth
 */
function flipEquiv(
    root1: TreeNode | null, 
    root2: TreeNode | null
): boolean {
    // Both null - equivalent
    if (root1 === null && root2 === null) {
        return true;
    }
    
    // One null, other not - not equivalent
    if (root1 === null || root2 === null) {
        return false;
    }
    
    // Values must match at corresponding positions
    if (root1.val !== root2.val) {
        return false;
    }
    
    // Two possibilities:
    // 1. No flip: left matches left, right matches right
    // 2. Flip: left matches right, right matches left
    
    const noFlip = flipEquiv(root1.left, root2.left) && 
                   flipEquiv(root1.right, root2.right);
    
    const withFlip = flipEquiv(root1.left, root2.right) && 
                     flipEquiv(root1.right, root2.left);
    
    return noFlip || withFlip;
}

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:

If we find a mismatch early, we prune
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.

Relationship to Graph Isomorphism

Practical Applications

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

1. React's Reconciliation Algorithm:

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.

Tree Comparison in Software Systems
Application	What's Compared	Algorithm Used	Why It Matters
React Virtual DOM	Old vs New tree	Structural diff	Minimal DOM updates
Git Tree Diff	Commit trees	Recursive comparison	Efficient changesets
Code Clone Detection	AST subtrees	Subtree matching	Find duplicated code
JSON Schema Validation	Instance vs Schema	Structural matching	Config correctness
XML Diff Tools	Document trees	Tree edit distance	Document comparison

Tree Edit Distance

Summary and Key Takeaways

Tree comparison problems reveal deep patterns in recursive thinking and structural analysis. Let's consolidate what we've learned:

Core Concepts Mastered

•Simultaneous recursion: Compare two tree positions together, recursing in lockstep
•Symmetry = Mirror comparison: Check left against right's reverse (cross-comparison)
•Equality = Direct comparison: Check left against left, right against right
•Subtree matching: Reduce to equality check at each potential root
•Flip equivalence: Allow both direct and crossed child matching at each node
•Serialization optimization: Convert trees to strings for fast pattern matching

The Core Pattern

All comparison problems follow this template:

function compare(t1, t2):
    if both null: return BASE_TRUE
    if one null: return BASE_FALSE
    if values don't match: return false
    return combine(
        compare(t1.left, WHICH_OF_T2),
        compare(t1.right, WHICH_OF_T2)
    )

The variation is in which t2 children we compare against and whether we use AND or OR to combine.

What's Next:

Page Complete