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

Concept Flow - Check if Two Trees are Symmetric

Start with two root nodes

↓

Check if both nodes are NULL?

Yes→Return True

No↓

Check if one node is NULL?

Yes→Return False

No↓

Check if node values are equal?

No→Return False

Yes↓

Recursively check left subtree of first with right subtree of second

↓

Recursively check right subtree of first with left subtree of second

↓

Return True if both recursive checks are True

↓

End

The process compares two trees node-by-node, checking if they are mirror images by recursively comparing opposite children.

Execution Sample

DSA C++

bool isSymmetric(TreeNode* t1, TreeNode* t2) {
  if (!t1 && !t2) return true;
  if (!t1 || !t2) return false;
  if (t1->val != t2->val) return false;
  return isSymmetric(t1->left, t2->right) && isSymmetric(t1->right, t2->left);
}

Checks if two trees are mirror images by comparing nodes and their opposite children recursively.

Execution Table

Step	t1 Node Value	t2 Node Value	Condition Checked	Result	Action Taken
1	1	1	Both NULL?	No	Check if one NULL
2	1	1	One NULL?	No	Check values equal
3	1	1	Values equal?	Yes	Recurse left-right and right-left
4	2	2	Both NULL?	No	Check one NULL
5	2	2	One NULL?	No	Check values equal
6	2	2	Values equal?	Yes	Recurse left-right and right-left
7	NULL	NULL	Both NULL?	Yes	Return True
8	NULL	NULL	Both NULL?	Yes	Return True
9	3	3	Both NULL?	No	Check one NULL
10	3	3	One NULL?	No	Check values equal
11	3	3	Values equal?	Yes	Recurse left-right and right-left
12	NULL	NULL	Both NULL?	Yes	Return True
13	NULL	NULL	Both NULL?	Yes	Return True
14	Return from left-right and right-left			True && True	Return True
15	Return from left-right and right-left			True && True	Return True
16	Return from root call			True && True	Trees are symmetric
17			End		Stop

💡 All corresponding nodes matched as mirror images, recursion ends with True

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 11	Final
t1 Node	Root(1)	Left(2)	Left NULL	Right(3)	N/A
t2 Node	Root(1)	Right(2)	Right NULL	Left(3)	N/A
Return Value	N/A	Pending	Pending	Pending	True

Key Moments - 3 Insights

Why do we check if both nodes are NULL first?

Because if both nodes are NULL, it means the subtrees are symmetric at this branch (see steps 7,8,12,13 in execution_table). This is the base case that stops recursion.

Why do we compare t1->left with t2->right and t1->right with t2->left?

Because symmetry means one tree's left subtree mirrors the other's right subtree (see step 3 and recursive calls in execution_table). This ensures mirror structure.

What happens if node values are not equal?

The function returns false immediately (step 6), because symmetric trees must have matching node values at mirrored positions.

Visual Quiz - 3 Questions

Look at the execution_table, what is the result of the condition 'Both NULL?' at step 7?

A No

B True

C Yes

D False

💡 Hint

Check the 'Condition Checked' and 'Result' columns at step 7 in execution_table

At which step does the function return false due to node value mismatch?

A No step returns false in this trace

B Step 11

C Step 6

D Step 2

💡 Hint

Look at the 'Action Taken' column in execution_table; no false return is shown

If t1->left was NULL but t2->right was not NULL at step 4, what would happen?

A Return true

B Return false

C Continue recursion

D Ignore and check values

💡 Hint

Refer to step 2 and 4 where one NULL node causes false return

Concept Snapshot

Check if two trees are symmetric by:
- Comparing root nodes
- Returning true if both NULL
- Returning false if one NULL
- Checking node values equality
- Recursively comparing left subtree of one with right subtree of other
- Return true only if all checks pass

Full Transcript

This concept checks if two trees are mirror images. We start by comparing the root nodes. If both nodes are NULL, they are symmetric here, so return true. If only one is NULL, return false because symmetry breaks. If node values differ, return false. Otherwise, recursively check the left subtree of the first tree against the right subtree of the second, and the right subtree of the first against the left subtree of the second. If both recursive checks return true, the trees are symmetric. The execution table shows step-by-step how nodes are compared and recursion proceeds until all nodes are checked or a mismatch is found.

Practice

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

easy

A. They have the same root value only.

B. They have the same number of nodes.

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 = A [OK]

Hint: Symmetric trees mirror each other perfectly [OK]

Common Mistakes:

• Thinking same number of nodes means symmetric
• Only comparing root values
• Ignoring structure when checking symmetry

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

easy

A. int isSymmetric(TreeNode* root1, TreeNode* root2);

B. bool isSymmetric(TreeNode* root1, TreeNode* root2);

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

D. bool isSymmetric(TreeNode root1, TreeNode root2);

Solution

1. Step 1: Identify correct return type

   The function should return a boolean indicating symmetry, so return type is bool.

2. Step 2: Use pointers for tree nodes

   Tree nodes are usually passed as pointers to avoid copying and to handle null nodes.

3. Final Answer:

   bool isSymmetric(TreeNode* root1, TreeNode* root2); -> Option B

4. Quick Check:

   Return bool and use pointers = C [OK]

Hint: Use bool return and pointers for tree nodes [OK]

Common Mistakes:

• Using void return type
• Passing nodes by value instead of pointer
• Using int instead of bool for result

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

#include <iostream>

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

bool isMirror(TreeNode* t1, TreeNode* t2) {
  if (!t1 && !t2) return true;
  if (!t1 || !t2) return false;
  return (t1->val == t2->val) && isMirror(t1->left, t2->right) && isMirror(t1->right, t2->left);
}

int main() {
  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);

  if (isMirror(root1, root2))
    std::cout << "Symmetric";
  else
    std::cout << "Not Symmetric";
  return 0;
}

medium

A. Symmetric

B. Not Symmetric

C. Compilation Error

D. Runtime Error

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

   Values match and recursive calls check left-right and right-left subtrees, confirming symmetry.

3. Final Answer:

   Symmetric -> Option A

4. Quick Check:

   Mirror check returns true = Symmetric [OK]

Hint: Check mirrored node values and subtree positions [OK]

Common Mistakes:

• Confusing left and right subtree checks
• Ignoring null node base cases
• Assuming same structure means symmetric

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

bool isMirror(TreeNode* t1, TreeNode* t2) {
  if (!t1 && !t2) return true;
  if (!t1 || !t2) return false;
  return (t1->val == t2->val) && isMirror(t1->left, t2->left) && isMirror(t1->right, t2->right);
}

medium

A. It uses incorrect return type.

B. It does not check for null nodes.

C. It returns true when both nodes are null.

D. It compares left subtree with left subtree instead of left with right.

Solution

1. Step 1: Review recursive calls for symmetry

   Symmetry requires comparing left subtree of one tree with right subtree of the other.

2. Step 2: Identify incorrect subtree comparisons

   The code compares left with left and right with right, which checks for identical trees, not symmetric.

3. Final Answer:

   It compares left subtree with left subtree instead of left with right. -> Option D

4. Quick Check:

   Mirror needs left-right swap, code misses it = D [OK]

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

Common Mistakes:

• Comparing same side subtrees instead of mirrored sides
• Ignoring null checks
• Confusing identical and symmetric trees

5. Given two binary trees, write a function that returns true if they are symmetric around their center. Which approach correctly solves this problem?

hard

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

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

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

D. Use a queue to perform level order traversal and compare nodes at each level without mirroring.

Solution

1. Step 1: Understand symmetry check logic

   Symmetry means one tree is mirror of the other, so compare left subtree of one with right subtree of other recursively.

2. Step 2: Evaluate other approaches

   Preorder traversal or node count alone do not guarantee symmetry; level order without mirroring misses mirror structure.

3. Final Answer:

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

4. Quick Check:

   Recursive mirror comparison solves symmetry = A [OK]

Hint: Recursively compare left with right subtree for symmetry [OK]

Common Mistakes:

• Using simple traversal without mirroring
• Comparing only node counts or root values
• Ignoring subtree structure in mirror form