Check if Two Trees are Symmetric in DSA C# - Execution Trace

Concept Flow - Check if Two Trees are Symmetric

Start with two root nodes

↓

Compare values of both nodes

↓

Check left subtree of 1 with right subtree of 2

↓

Check right subtree of 1 with left subtree of 2

↓

Both subtrees symmetric?

↓

Return True

Start by comparing the root nodes of two trees. If their values match, recursively check if the left subtree of one matches the right subtree of the other and vice versa. Return true only if all corresponding pairs are symmetric.

Execution Sample

DSA C#

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

This code checks if two trees are mirror images by comparing node values and recursively checking opposite children.

Execution Table

Step	t1 Node Value	t2 Node Value	Condition Checked	Result	Next Action
1	1	1	Both null? (No)	Continue	Check values equal
2	1	1	Values equal? (Yes)	Continue	Check AreSymmetric(t1.left, t2.right)
3	2	2	Both null? (No)	Continue	Check values equal
4	2	2	Values equal? (Yes)	Continue	Check AreSymmetric(t1.left.left, t2.right.right)
5	null	null	Both null? (Yes)	True	Return True for this call
6	null	null	Both null? (Yes)	True	Return True for this call
7	2	2	Left and right subtrees symmetric? (Yes)	True	Return True for this call
8	3	3	Both null? (No)	Continue	Check values equal
9	3	3	Values equal? (Yes)	Continue	Check AreSymmetric(t1.right.left, t2.left.right)
10	null	null	Both null? (Yes)	True	Return True for this call
11	null	null	Both null? (Yes)	True	Return True for this call
12	3	3	Left and right subtrees symmetric? (Yes)	True	Return True for this call
13	1	1	Left and right subtrees symmetric? (Yes)	True	Return True for root call
14	N/A	N/A	All checks passed	True	Trees are symmetric

💡 All corresponding nodes matched or were null, confirming symmetry

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 7	After Step 9	After Step 12	Final
t1 Node	Root(1)	Left(2)	Left.Left(null)	Right(3)	Right.Left(null)	Root(1)	Root(1)
t2 Node	Root(1)	Right(2)	Right.Right(null)	Left(3)	Left.Right(null)	Root(1)	Root(1)
Result	N/A	Continue	True	Continue	Continue	True	True

Key Moments - 3 Insights

Why do we check if both nodes are null first?

Because if both nodes are null, it means those branches ended symmetrically. This is shown in execution_table rows 5, 6, 10, and 11 where both nodes are null and return True.

What happens if one node is null and the other is not?

The function returns False immediately because the trees differ in structure. This is implied in the code and would stop recursion early, though not shown in this symmetric example.

Why do we compare t1.left with t2.right and t1.right with t2.left?

Because symmetry means one tree's left side mirrors the other's right side. This cross comparison is the core logic, visible in steps 2, 4, 7, 9, and 12.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the result when both nodes are null?

A True

B False

C Continue

D Error

💡 Hint

Check the 'Result' column at step 5 in execution_table

At which step does the function confirm the root nodes have equal values?

A Step 1

B Step 13

C Step 2

D Step 14

💡 Hint

Look at the 'Condition Checked' column for value comparison in execution_table

If t1.left was null but t2.right was not, what would happen in the execution?

A Return True

B Return False

C Continue checking

D Throw exception

💡 Hint

Refer to the key moment about one node null and the other not

Concept Snapshot

Check if Two Trees are Symmetric:
- Compare root nodes values.
- Recursively check t1.left with t2.right and t1.right with t2.left.
- If both nodes null, return true.
- If one null and other not, return false.
- Return true only if all pairs match symmetrically.

Full Transcript

This concept checks if two trees are mirror images. We start by comparing the root nodes. If both are null, they are symmetric at that branch. If one is null and the other is not, they are not symmetric. If values match, we recursively check the left subtree of the first tree with the right subtree of the second, and the right subtree of the first with the left subtree of the second. This cross-check ensures symmetry. The execution table shows step-by-step how nodes are compared and how the function returns true only when all corresponding nodes match or are null. Key moments clarify why null checks come first and why cross comparisons are necessary. The visual quiz tests understanding of these steps and outcomes.

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