Check if Two Trees are Symmetric in DSA Java - Execution Trace

Concept Flow - Check if Two Trees are Symmetric

Start with two root nodes

↓

Are both nodes null?

Yes→Return True

No↓

Is one node null?

Yes→Return False

No↓

Are node values equal?

No→Return False

Yes↓

Check left subtree of first with right subtree of second

↓

Check right subtree of first with left subtree of second

↓

Return True if both checks True, else False

The flow compares two nodes step-by-step, checking nulls and values, then recursively checks opposite subtrees for symmetry.

Execution Sample

DSA Java

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

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

Execution Table

Step	t1.val	t2.val	Condition Checked	Result	Next Action
1	1	1	Both null? (No)	False	Check one null?
2	1	1	One null? (No)	False	Check values equal?
3	1	1	Values equal? (Yes)	True	Check left-right subtrees
4	2	2	Both null? (No)	False	Check one null?
5	2	2	One null? (No)	False	Check values equal?
6	2	2	Values equal? (Yes)	True	Check left-right subtrees
7	null	null	Both null? (Yes)	True	Return True
8	null	null	Both null? (Yes)	True	Return True
9	3	3	Both null? (No)	False	Check one null?
10	3	3	One null? (No)	False	Check values equal?
11	3	3	Values equal? (Yes)	True	Check left-right subtrees
12	null	null	Both null? (Yes)	True	Return True
13	null	null	Both null? (Yes)	True	Return True
14	null	null	Both null? (Yes)	True	Return True
15	null	null	Both null? (Yes)	True	Return True
16	Return final result			True	Trees are symmetric

💡 All node pairs matched symmetrically or were both null, so function returns True.

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 11	Final
t1.val	1	2	3	null	null
t2.val	1	2	3	null	null
Result	N/A	True	True	True	True

Key Moments - 3 Insights

Why do we check if both nodes are null first?

Because if both nodes are null, it means this part of the trees matches perfectly (see steps 7,8,12-15). This is a base case that returns True immediately.

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

The function returns False immediately (step 2), because one side missing means trees are not symmetric.

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

This checks mirror symmetry: left subtree of one tree must match right subtree of the other (steps 3,6,11).

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the result of comparing t1.val and t2.val?

A True

B False

C Null

D Not checked

💡 Hint

Check the 'Result' column at step 3 in execution_table

At which step does the function return True because both nodes are null?

A Step 2

B Step 3

C Step 7

D Step 16

💡 Hint

Look for 'Both null? (Yes)' and 'Return True' 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 Cause error

💡 Hint

Refer to step 2 logic where one node null and other not returns False

Concept Snapshot

Check if two trees are symmetric by:
- Comparing root nodes for equality
- Returning True if both nodes are null
- Returning False if only one is null
- Recursively checking left subtree of one with right subtree of other
- Recursively checking right subtree of one with left subtree of other
- Return True only if all checks pass

Full Transcript

This concept shows how to check if two trees are mirror images. We start by comparing the root nodes. If both are null, we return True because empty trees are symmetric. If only one is null, we return False because symmetry breaks. If both nodes exist, we check if their values are equal. Then, we recursively check the left child of the first tree against the right child of the second tree, and the right child of the first tree against the left child of the second tree. If all these checks pass, the trees are symmetric. The execution table traces these steps with node values and conditions, showing how the function returns True or False at each step. The variable tracker shows how node values and results change during recursion. Key moments clarify why null checks come first and why opposite children are compared. The quiz tests understanding of these steps. This method ensures a full mirror check of two trees.

Practice

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

easy

A. They have identical left subtrees only.

B. They have the same number of nodes.

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

D. They have the same root value 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 = D [OK]

Hint: Symmetric trees mirror each other exactly [OK]

Common Mistakes:

• Thinking same number of nodes means symmetric
• Only comparing root values
• Ignoring structure differences

2. Which Java method signature correctly defines a function to check if two trees are symmetric?

easy

A. public boolean isSymmetric(TreeNode root1, TreeNode root2)

B. boolean isSymmetric(TreeNode root1, TreeNode root2) {}

C. public void isSymmetric(TreeNode root1, TreeNode root2)

D. public boolean isSymmetric(TreeNode root)

Solution

1. Step 1: Identify correct return type and parameters

   The method should return boolean and accept two TreeNode parameters for two trees.

2. Step 2: Check method signature syntax

   Public access, boolean return, and parameter types match in public boolean isSymmetric(TreeNode root1, TreeNode root2).

3. Final Answer:

   public boolean isSymmetric(TreeNode root1, TreeNode root2) -> Option A

4. Quick Check:

   Correct signature returns boolean with two TreeNode inputs [OK]

Hint: Boolean return with two TreeNode inputs is needed [OK]

Common Mistakes:

• Using void return type
• Missing public keyword
• Using only one TreeNode parameter

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

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

System.out.println(isSymmetric(root1, root2));

public static boolean isSymmetric(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) return true;
    if (t1 == null || t2 == null) return false;
    return (t1.val == t2.val) && isSymmetric(t1.left, t2.right) && isSymmetric(t1.right, t2.left);
}

medium

A. Runtime exception

B. false

C. Compilation error

D. true

Solution

1. Step 1: Analyze tree structure and values

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

2. Step 2: Trace recursive calls

   Values match and recursive calls check mirrored children, all return true.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Mirror structure and values = true [OK]

Hint: Check mirrored nodes and values recursively [OK]

Common Mistakes:

• Ignoring mirrored child comparison
• Confusing left and right children
• Assuming same structure means false

4. Identify the bug in this code snippet that checks if two trees are symmetric:

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

medium

A. It compares left with left and right with right instead of mirrored children.

B. It does not check for null nodes.

C. It returns true when both nodes are null.

D. It uses incorrect return type.

Solution

1. Step 1: Review recursive calls for symmetry

   The code compares t1.left with t2.left and t1.right with t2.right, which checks identical structure, not mirror.

2. Step 2: Identify correct mirrored comparison

   It should compare t1.left with t2.right and t1.right with t2.left for symmetry.

3. Final Answer:

   It compares left with left and right with right instead of mirrored children. -> Option A

4. Quick Check:

   Mirror check needs cross child comparison [OK]

Hint: Mirror check swaps left and right children [OK]

Common Mistakes:

• Comparing same side children instead of mirrored
• Ignoring null checks
• Wrong return type usage

5. Given two binary trees, write a Java method to check if they are symmetric. Which approach correctly solves this problem? A) Traverse both trees in preorder and compare node values in order. B) Recursively check if left subtree of first tree is mirror of right subtree of second tree and vice versa. C) Compare the height of both trees and return true if equal. D) Check if both trees have the same number of leaf nodes.

hard

A. Traverse both trees in preorder and compare node values in order.

B. Recursively check if left subtree of first tree is mirror of right subtree of second tree and vice versa.

C. Compare the height of both trees and return true if equal.

D. Check if both trees have the same number of leaf nodes.

Solution

1. Step 1: Understand symmetry check requirements

   Symmetry means one tree is mirror image of the other, so left subtree of one matches right subtree of other.

2. Step 2: Evaluate approaches

   Recursively check if left subtree of first tree is mirror of right subtree of second tree and vice versa. correctly uses recursive mirror checks; others ignore structure or order.

3. Final Answer:

   Recursively check if left subtree of first tree is mirror of right subtree of second tree and vice versa. -> Option B

4. Quick Check:

   Mirror recursive check solves symmetry [OK]

Hint: Mirror recursive check is key to symmetry [OK]

Common Mistakes:

• Using preorder traversal comparison
• Comparing only height or leaf counts
• Ignoring mirrored subtree checks