Check if Two Trees are Symmetric in DSA C - 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↓

Do nodes have same value?

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 AND of both subtree checks

The function compares two trees by checking root values and recursively comparing left subtree of one with right subtree of the other, ensuring mirror symmetry.

Execution Sample

DSA C

bool isSymmetric(TreeNode* t1, TreeNode* t2) {
  if (!t1 && !t2) return true;
  if (!t1 || !t2) 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 subtrees.

Execution Table

Step	t1 Node Value	t2 Node Value	Condition Checked	Result	Next Action
1	1	1	Both NULL? No; One NULL? No; Values equal? Yes	True	Check left subtree of t1 with right subtree of t2
2	2	2	Both NULL? No; One NULL? No; Values equal? Yes	True	Check left subtree of t1 with right subtree of t2
3	3	3	Both NULL? No; One NULL? No; Values equal? Yes	True	Check left subtree of t1 with right subtree of t2
4	NULL	NULL	Both NULL? Yes	True	Return True
5	NULL	NULL	Both NULL? Yes	True	Return True
6	NULL	NULL	Both NULL? Yes	True	Return True
7	NULL	NULL	Both NULL? Yes	True	Return True
8	3	3	Both NULL? No; One NULL? No; Values equal? Yes	True	Check right subtree of t1 with left subtree of t2
9	NULL	NULL	Both NULL? Yes	True	Return True
10	NULL	NULL	Both NULL? Yes	True	Return True
11	2	2	Both NULL? No; One NULL? No; Values equal? Yes	True	Check right subtree of t1 with left subtree of t2
12	NULL	NULL	Both NULL? Yes	True	Return True
13	NULL	NULL	Both NULL? Yes	True	Return True
14	1	1	All subtree checks True	True	Return True
15	-	-	All checks done	True	Trees are symmetric

💡 All corresponding nodes matched and subtree checks returned true, confirming symmetry

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 11	Final
t1 Node	Root(1)	Left(2)	Left(3)	Right(3)	Right(2)	NULL
t2 Node	Root(1)	Right(2)	Right(3)	Left(3)	Left(2)	NULL
Result	N/A	True	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 the subtree ends symmetrically here, so we return True immediately (see execution_table rows 4,5,6,7).

Why do we compare t1->val with t2->val?

Because for symmetry, the values must be equal at corresponding nodes. If they differ, we return False immediately (see execution_table step 1).

Why do we compare t1's left subtree with t2's right subtree?

Because symmetry means mirror image, so left of one tree matches right of the other (see concept_flow and execution_table steps 2 and 8).

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the value of t1 Node?

A 3

B 2

C 1

D NULL

💡 Hint

Check the 't1 Node Value' column at step 3 in execution_table

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

A Step 1

B Step 8

C Step 4

D Step 14

💡 Hint

Look for rows where 'Condition Checked' is 'Both NULL? Yes' and 'Result' is True

If t1->val and t2->val differ at the root, what would happen?

A The function continues checking subtrees

B The function returns False immediately

C The function returns True

D The function crashes

💡 Hint

Refer to execution_table step 1 where values are compared for equality

Concept Snapshot

Check if Two Trees are Symmetric

- Compare two nodes: if both NULL, return true
- If one NULL, return false
- Check if values equal
- Recursively check left subtree of first with right subtree of second and vice versa
- Return true only if all checks pass

Full Transcript

This concept shows how to check if two trees are symmetric by comparing nodes in a mirror fashion. We start by checking if both nodes are NULL, which means symmetry at that point. If only one is NULL, symmetry breaks. Then we compare node values. If they match, we recursively check the left subtree of the first tree with the right subtree of the second tree, and the right subtree of the first with the left subtree of the second. If all these checks return true, the trees are symmetric.

Practice

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

easy

A. They are mirror images of each other around their roots

B. They have the same number of nodes

C. They have the same preorder traversal

D. They have the same height

Solution

1. Step 1: Understand symmetry in trees

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

2. Step 2: Compare with other options

   Having the same number of nodes, preorder traversal, or height does not guarantee mirror symmetry.

3. Final Answer:

   They are mirror images of each other around their roots -> Option A

4. Quick Check:

   Symmetry means mirror image = A [OK]

Hint: Symmetric trees mirror each other around the root [OK]

Common Mistakes:

• Confusing same size with symmetry
• Thinking same traversal means symmetric
• Assuming same height means symmetric

2. Which of the following C function signatures is correct to check if two trees are symmetric?

easy

A. int isSymmetric(struct Node* root1, struct Node* root2);

B. void isSymmetric(struct Node root1, struct Node root2);

C. int isSymmetric(struct Node root1, struct Node root2);

D. int isSymmetric(Node* root1, Node root2);

Solution

1. Step 1: Understand pointer usage in C for trees

   Tree nodes are accessed via pointers, so parameters must be pointers to struct Node.

2. Step 2: Analyze each option

   int isSymmetric(struct Node* root1, struct Node* root2); uses pointers correctly and returns int for boolean result. Options A and B pass structs by value, which is inefficient and incorrect. int isSymmetric(Node* root1, Node root2); mixes pointer and non-pointer types incorrectly.

3. Final Answer:

   int isSymmetric(struct Node* root1, struct Node* root2); -> Option A

4. Quick Check:

   Use pointers for tree nodes in C function [OK]

Hint: Use pointers to struct Node for tree parameters [OK]

Common Mistakes:

• Passing structs by value instead of pointers
• Mixing pointer and non-pointer parameters
• Using void return type instead of int for boolean

3. What will be the output of the following code snippet checking symmetry of two trees?

struct Node {
  int val;
  struct Node* left;
  struct Node* right;
};

int isMirror(struct Node* t1, struct Node* t2) {
  if (!t1 && !t2) return 1;
  if (!t1 || !t2) return 0;
  return (t1->val == t2->val) && isMirror(t1->left, t2->right) && isMirror(t1->right, t2->left);
}

int main() {
  struct Node n1 = {1, NULL, NULL};
  struct Node n2 = {1, NULL, NULL};
  printf("%d", isMirror(&n1, &n2));
  return 0;
}

medium

A. 0

B. 1

C. Compilation error

D. Runtime error

Solution

1. Step 1: Analyze base cases and node values

   Both nodes have value 1 and no children, so both left and right pointers are NULL.

2. Step 2: Evaluate recursive calls

   isMirror returns 1 if both nodes are NULL (true). Since both left and right children are NULL, recursive calls return 1. Values match, so overall returns 1.

3. Final Answer:

   1 -> Option B

4. Quick Check:

   Identical single nodes are symmetric = 1 [OK]

Hint: Single nodes with same value are symmetric [OK]

Common Mistakes:

• Confusing NULL children as asymmetric
• Expecting 0 for identical nodes
• Misreading recursive base cases

4. Identify the bug in this function to check if two trees are symmetric:

int isMirror(struct Node* t1, struct Node* t2) {
  if (t1 == NULL && t2 == NULL) return 1;
  if (t1 == NULL || t2 == NULL) return 0;
  if (t1->val != t2->val) return 0;
  return isMirror(t1->left, t2->left) && isMirror(t1->right, t2->right);
}

medium

A. Should use OR instead of AND in return statement

B. Missing check for NULL nodes

C. Return type should be void

D. Should compare t1->left with t2->right and t1->right with t2->left

Solution

1. Step 1: Understand mirror symmetry check

   Mirror symmetry requires left subtree of one tree to match right subtree of the other and vice versa.

2. Step 2: Identify incorrect recursive calls

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

3. Final Answer:

   Should compare t1->left with t2->right and t1->right with t2->left -> Option D

4. Quick Check:

   Mirror means cross compare left and right subtrees [OK]

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

Common Mistakes:

• Comparing left with left and right with right
• Ignoring NULL checks
• Using wrong logical operators

5. Given two binary trees, how would you implement a function to check if they are symmetric using a queue (iterative approach)? Which step is essential in this approach?

hard

A. Compare only root nodes and ignore children

B. Traverse both trees in preorder and compare arrays

C. Enqueue pairs of nodes to compare left of one with right of other

D. Use a stack to store nodes from only one tree

Solution

1. Step 1: Understand iterative symmetry check

   Use a queue to store pairs of nodes to compare their values and subtrees iteratively.

2. Step 2: Identify correct node pairing

   Pairs must be left child of one tree with right child of the other to check mirror symmetry.

3. Step 3: Reject incorrect approaches

   Preorder traversal comparison or using stack for one tree only does not check mirror symmetry. Ignoring children misses the point.

4. Final Answer:

   Enqueue pairs of nodes to compare left of one with right of other -> Option C

5. Quick Check:

   Queue pairs left-right nodes for iterative mirror check [OK]

Hint: Queue pairs left and right nodes to check symmetry iteratively [OK]

Common Mistakes:

• Comparing same side children instead of opposite
• Using preorder traversal arrays
• Ignoring children nodes in comparison