Check if Two Trees are Symmetric in DSA Go

Mental Model

Two trees are symmetric if one is a mirror image of the other, meaning their shapes and node values match when flipped.

Analogy: Imagine holding two identical tree-shaped paper cutouts. If you flip one over and it fits exactly on the other, they are symmetric.

Tree1:       1           Tree2:       1
           /   \                   /   \
          2     3                 3     2
         /       \               /       \
        4         5             5         4

Symmetry means Tree2 is Tree1 flipped left to right.

Dry Run Walkthrough

Input: Tree1: 1->2->4 and 1->3->5, Tree2: 1->3->5 and 1->2->4 (mirror structure)

Goal: Check if Tree2 is the mirror image of Tree1

Step 1: Compare root nodes of both trees (1 and 1)

Tree1 root=1, Tree2 root=1

Why: Roots must match for symmetry

Step 2: Compare left child of Tree1 (2) with right child of Tree2 (2)

Tree1 left=2, Tree2 right=2

Why: Mirror means left of one equals right of other

Step 3: Compare right child of Tree1 (3) with left child of Tree2 (3)

Tree1 right=3, Tree2 left=3

Why: Mirror means right of one equals left of other

Step 4: Compare left child of Tree1's left (4) with right child of Tree2's right (4)

Tree1 left.left=4, Tree2 right.right=4

Why: Mirror symmetry continues down the tree

Step 5: Compare right child of Tree1's right (5) with left child of Tree2's left (5)

Tree1 right.right=5, Tree2 left.left=5

Why: Mirror symmetry continues down the tree

Result:

Trees are symmetric because all corresponding nodes match in mirror positions

Annotated Code

DSA Go

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func isSymmetric(t1 *TreeNode, t2 *TreeNode) bool {
    if t1 == nil && t2 == nil {
        return true
    }
    if t1 == nil || t2 == nil {
        return false
    }
    if t1.Val != t2.Val {
        return false
    }
    // Recursively check left of t1 with right of t2 and right of t1 with left of t2
    return isSymmetric(t1.Left, t2.Right) && isSymmetric(t1.Right, t2.Left)
}

func main() {
    // Construct Tree1
    t1 := &TreeNode{Val: 1}
    t1.Left = &TreeNode{Val: 2}
    t1.Right = &TreeNode{Val: 3}
    t1.Left.Left = &TreeNode{Val: 4}
    t1.Right.Right = &TreeNode{Val: 5}

    // Construct Tree2 (mirror of Tree1)
    t2 := &TreeNode{Val: 1}
    t2.Left = &TreeNode{Val: 3}
    t2.Right = &TreeNode{Val: 2}
    t2.Left.Left = &TreeNode{Val: 5}
    t2.Right.Right = &TreeNode{Val: 4}

    if isSymmetric(t1, t2) {
        fmt.Println("Trees are symmetric")
    } else {
        fmt.Println("Trees are not symmetric")
    }
}

if t1 == nil && t2 == nil { return true }

both nodes are empty means symmetry at this branch

if t1 == nil || t2 == nil { return false }

one node empty but other not means asymmetry

if t1.Val != t2.Val { return false }

node values must match for symmetry

return isSymmetric(t1.Left, t2.Right) && isSymmetric(t1.Right, t2.Left)

check mirror children recursively

Output

Trees are symmetric

Complexity Analysis

Time: O(n) because we visit each node once to compare

Space: O(h) due to recursion stack where h is tree height

vs Alternative: Compared to flattening trees to arrays and comparing, this uses less space and is faster by checking structure directly

Edge Cases

Both trees are empty

Returns true because empty trees are symmetric

DSA Go

if t1 == nil && t2 == nil { return true }

One tree is empty, other is not

Returns false because structure differs

DSA Go

if t1 == nil || t2 == nil { return false }

Trees have different values at corresponding nodes

Returns false due to value mismatch

DSA Go

if t1.Val != t2.Val { return false }

When to Use This Pattern

When a problem asks if two trees are mirror images or symmetric, use recursive comparison of opposite children to verify symmetry.

Common Mistakes

Mistake: Comparing left child of one tree with left child of the other instead of opposite sides
Fix: Compare left child of first tree with right child of second tree and vice versa

Summary

Checks if two trees are mirror images of each other by comparing nodes recursively.

Use when you need to verify if one tree is the symmetric reflection of another.

The key insight is to compare left subtree of one tree with right subtree of the other recursively.