Check if Two Trees are Symmetric in DSA C#

Mental Model

Two trees are symmetric if one is a mirror image of the other. We check if the left side of one tree matches the right side of the other and vice versa.

Analogy: Imagine folding a paper with a drawing on one side. If the drawing perfectly matches on the other side when folded, the two sides are symmetric.

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

Pointers:
  ↑ root1           ↑ root2

Dry Run Walkthrough

Input: Tree1: 1->2,3->4,null; Tree2: 1->3,2->null,4

Goal: Check if Tree1 and Tree2 are mirror images (symmetric).

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

Tree1: 1 -> 2,3 -> 4,null
Tree2: 1 -> 3,2 -> null,4

Why: Roots must be equal to start symmetry check.

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

Tree1 left: 2 -> 4,null
Tree2 right: 2 -> null,4

Why: Left of one tree must match right of the other.

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

Tree1 right: 3 -> null,null
Tree2 left: 3 -> null,null

Why: Right of one tree must match left of the other.

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

Tree1 left.left: 4 -> null,null
Tree2 right.right: 4 -> null,null

Why: Leaves must match in mirror positions.

Step 5: Check null children pairs for symmetry.

All corresponding children pairs are null.

Why: Null children pairs confirm symmetry at leaves.

Result:

Trees are symmetric (mirror images).

Annotated Code

DSA C#

using System;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public bool AreSymmetric(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) return true; // both empty
        if (root1 == null || root2 == null) return false; // one empty
        if (root1.val != root2.val) return false; // values differ

        // check mirror symmetry recursively
        return AreSymmetric(root1.left, root2.right) && AreSymmetric(root1.right, root2.left);
    }

    public static void Main() {
        // Construct Tree1: 1
        //               /   \
        //              2     3
        //             /       \
        //            4         null
        TreeNode tree1 = new TreeNode(1,
            new TreeNode(2, new TreeNode(4), null),
            new TreeNode(3));

        // Construct Tree2: 1
        //               /   \
        //              3     2
        //                   / \
        //                 null 4
        TreeNode tree2 = new TreeNode(1,
            new TreeNode(3),
            new TreeNode(2, null, new TreeNode(4)));

        Solution sol = new Solution();
        bool result = sol.AreSymmetric(tree1, tree2);
        Console.WriteLine(result ? "Trees are symmetric" : "Trees are not symmetric");
    }
}

if (root1 == null && root2 == null) return true;

both nodes empty means symmetry at this branch

if (root1 == null || root2 == null) return false;

one node empty means asymmetry

if (root1.val != root2.val) return false;

values must match for symmetry

return AreSymmetric(root1.left, root2.right) && AreSymmetric(root1.right, root2.left);

recursively check mirror children pairs

Output

Trees are symmetric

Complexity Analysis

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

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

vs Alternative: Compared to iterative approaches, recursion is simpler and direct for symmetry checks but uses call stack space

Edge Cases

Both trees are empty

Returns true because empty trees are symmetric

DSA C#

if (root1 == null && root2 == null) return true;

One tree is empty, other is not

Returns false because symmetry is broken

DSA C#

if (root1 == null || root2 == null) return false;

Trees have different root values

Returns false immediately

DSA C#

if (root1.val != root2.val) return false;

When to Use This Pattern

When a problem asks if two trees are mirror images or symmetric, use recursive checks comparing left subtree of one with right subtree of the other.

Common Mistakes

Mistake: Comparing left subtree with left subtree instead of left with right
Fix: Compare root1.left with root2.right and root1.right with root2.left

Summary

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

Use when you need to verify if two trees are symmetric in structure and values.

The key is to compare left subtree of one tree with right subtree of the other and vice versa.

Practice

1. What does it mean for two binary trees to be symmetric?

easy

A. They have the same number of nodes.

B. They have the same root value only.

C. They are mirror images of each other around their center.

D. They have identical left subtrees only.

Solution

1. Step 1: Understand symmetry in trees

   Two trees are symmetric if one is the mirror reflection of the other around the center.

2. Step 2: Compare structure and node values

   Both structure and node values must match in a mirrored way for symmetry.

3. Final Answer:

   They are mirror images of each other around their center. -> Option C

4. Quick Check:

   Symmetry means mirror image [OK]

Hint: Symmetric trees mirror each other exactly [OK]

Common Mistakes:

• Thinking symmetry means identical trees
• Only comparing root values
• Ignoring structure in comparison

2. Which of the following C# method signatures correctly represents a function to check if two trees are symmetric?

easy

A. public void IsSymmetric(TreeNode root1, TreeNode root2)

B. public int IsSymmetric(TreeNode root1, TreeNode root2)

C. public string IsSymmetric(TreeNode root1, TreeNode root2)

D. public bool IsSymmetric(TreeNode root1, TreeNode root2)

Solution

1. Step 1: Determine return type for symmetry check

   The function should return true or false, so return type must be bool.

2. Step 2: Check method signature correctness

   Method with signature public bool IsSymmetric(TreeNode root1, TreeNode root2) matches expected usage.

3. Final Answer:

   public bool IsSymmetric(TreeNode root1, TreeNode root2) -> Option D

4. Quick Check:

   Return type bool for true/false [OK]

Hint: Symmetry check returns true or false, so use bool [OK]

Common Mistakes:

• Using void return type
• Returning int or string instead of bool
• Incorrect parameter types

3. What will be the output of the following C# code snippet?

class TreeNode {
  public int val;
  public TreeNode left, right;
  public TreeNode(int x) { val = x; }
}

bool IsMirror(TreeNode t1, TreeNode t2) {
  if (t1 == null && t2 == null) return true;
  if (t1 == null || t2 == null) return false;
  return (t1.val == t2.val) && IsMirror(t1.left, t2.right) && IsMirror(t1.right, t2.left);
}

TreeNode root1 = new TreeNode(1);
root1.left = new TreeNode(2);
root1.right = new TreeNode(3);

TreeNode root2 = new TreeNode(1);
root2.left = new TreeNode(3);
root2.right = new TreeNode(2);

Console.WriteLine(IsMirror(root1, root2));

medium

A. True

B. False

C. Compilation error

D. Runtime exception

Solution

1. Step 1: Analyze tree structures

   root1 has left=2, right=3; root2 has left=3, right=2, which are mirror images.

2. Step 2: Trace IsMirror function calls

   IsMirror compares root values (1==1), then left of root1 with right of root2 (2==2), and right of root1 with left of root2 (3==3), all true.

3. Final Answer:

   True -> Option A

4. Quick Check:

   Mirror check returns true [OK]

Hint: Mirror check compares opposite children recursively [OK]

Common Mistakes:

• Confusing left and right children
• Assuming identical structure means symmetric
• Ignoring null checks

4. Identify the bug in the following C# method that checks if two trees are symmetric:

bool IsMirror(TreeNode t1, TreeNode t2) {
  if (t1 == null || t2 == null) return true;
  if (t1.val != t2.val) return false;
  return IsMirror(t1.left, t2.right) && IsMirror(t1.right, t2.left);
}

medium

A. The first if condition should return false if one node is null and the other is not.

B. The method should return void instead of bool.

C. The comparison t1.val != t2.val is incorrect and should be reversed.

D. The recursive calls should compare t1.left with t2.left and t1.right with t2.right.

Solution

1. Step 1: Check null node handling

   If one node is null and the other is not, trees are not symmetric, so should return false, not true.

2. Step 2: Verify other conditions

   Value comparison and recursive calls are correct for mirror checking.

3. Final Answer:

   The first if condition should return false if one node is null and the other is not. -> Option A

4. Quick Check:

   Null mismatch means false [OK]

Hint: Return false if only one node is null [OK]

Common Mistakes:

• Returning true when one node is null
• Mixing up recursive child comparisons
• Incorrect return types

5. Given two binary trees, write a method to check if they are symmetric around their center. Which approach below correctly solves this problem efficiently?

hard

A. Use a queue to perform level order traversal and compare nodes at each level from left to right.

B. Use a recursive helper that compares left subtree of first tree with right subtree of second tree and vice versa.

C. Check if both trees have the same number of nodes and same root value only.

D. Traverse both trees in preorder and compare the traversal lists for equality.

Solution

1. Step 1: Understand symmetry check logic

   Symmetry means left subtree of one tree matches right subtree of the other and vice versa.

2. Step 2: Evaluate approaches

   Recursive helper comparing opposite subtrees is efficient and correct. Preorder or level order traversals do not capture mirror structure properly.

3. Final Answer:

   Use a recursive helper that compares left subtree of first tree with right subtree of second tree and vice versa. -> Option B

4. Quick Check:

   Mirror recursion solves symmetry [OK]

Hint: Compare opposite subtrees recursively for symmetry [OK]

Common Mistakes:

• Comparing same side subtrees instead of opposite
• Using traversal equality which misses mirror structure
• Ignoring node values in comparison