Check if Two Trees are Symmetric in DSA C - Deep Dive

Overview - Check if Two Trees are Symmetric

What is it?

Checking if two trees are symmetric means verifying if one tree is a mirror image of the other. This involves comparing nodes in both trees to see if they match in value and position when flipped. It helps us understand if the structure and values of two trees reflect each other perfectly. This concept is important in many tree-related problems and algorithms.

Why it matters

Without the ability to check symmetry, we would struggle to identify balanced or mirrored structures in data, which are common in graphics, decision trees, and network topologies. Symmetry checks help optimize algorithms and ensure data integrity in hierarchical systems. Without this, many applications would be less efficient or incorrect when handling mirrored data.

Where it fits

Before learning this, you should understand basic tree structures and how to traverse them. After mastering symmetry checks, you can explore more complex tree problems like balanced trees, subtree checks, and tree serialization.

Mental Model

Core Idea

Two trees are symmetric if one is the mirror image of the other, meaning their nodes match in value and position when flipped.

Think of it like...

Imagine two hands facing each other palm to palm. If one hand is the exact mirror of the other, every finger lines up perfectly but reversed. Checking tree symmetry is like checking if two hands are mirror images.

Tree1:           Tree2 (mirror)
    1                 1
   / \               / \
  2   3             3   2
 /     \           /     \
4       5         5       4

Build-Up - 7 Steps

1

Foundation

Understand Basic Tree Structure

Concept: Introduce what a binary tree is and how nodes connect.

A binary tree is a structure where each node has up to two children: left and right. Each node holds a value. Trees start from a root node and branch out. For example, a root node with value 1 can have left child 2 and right child 3.

Result

You can visualize and represent trees with nodes and links.

Understanding the basic tree structure is essential because symmetry depends on comparing nodes and their positions.

2

Foundation

Learn Tree Traversal Basics

Concept: Introduce how to visit nodes in a tree systematically.

Traversal means visiting nodes in a specific order. Common ways are preorder (root-left-right), inorder (left-root-right), and postorder (left-right-root). Traversal helps us access and compare nodes.

Result

You can visit every node in a tree in a predictable order.

Knowing traversal methods is key to comparing nodes between two trees for symmetry.

3

Intermediate

Define Mirror Image Concept for Trees

Concept: Explain what it means for one tree to be the mirror of another.

Two trees are mirrors if the left subtree of one matches the right subtree of the other and vice versa, and their node values are equal. This means flipping one tree horizontally would make it look like the other.

Result

You understand the condition to check symmetry between two trees.

Recognizing the mirror relationship guides how to compare nodes recursively.

4

Intermediate

Implement Recursive Symmetry Check

🤔Before reading on: do you think checking symmetry requires comparing nodes in the same position or opposite positions? Commit to your answer.

Concept: Use recursion to compare nodes in opposite positions of two trees.

Write a function that takes two nodes. If both are null, they match. If one is null or values differ, they don't. Otherwise, recursively check left child of first with right child of second, and right child of first with left child of second.

Result

You can determine if two trees are symmetric by recursive calls.

Understanding recursion here simplifies the problem by breaking it into smaller symmetric checks.

5

Intermediate

Handle Edge Cases in Symmetry

🤔Before reading on: do you think empty trees are symmetric? Commit to yes or no.

Concept: Consider cases like empty trees, single nodes, and unbalanced trees.

If both trees are empty, they are symmetric. If only one is empty, they are not. Single node trees are symmetric with themselves. Unbalanced trees fail symmetry if their structure differs.

Result

You can correctly handle all input cases without errors.

Handling edge cases prevents bugs and ensures your function works universally.

6

Advanced

Optimize Symmetry Check with Iteration

🤔Before reading on: do you think recursion is the only way to check symmetry? Commit to yes or no.

Concept: Use a queue or stack to check symmetry iteratively instead of recursion.

Use a queue to store pairs of nodes to compare. While queue not empty, pop a pair, check values and children. Push children pairs in opposite order. This avoids recursion and stack overflow.

Result

You can check symmetry efficiently without recursion.

Knowing iterative methods helps handle very deep trees and improves performance.

7

Expert

Understand Symmetry in Non-Binary Trees

🤔Before reading on: do you think symmetry checking applies only to binary trees? Commit to yes or no.

Concept: Extend symmetry concept to trees with more than two children per node.

For trees with multiple children, symmetry means children lists are mirror images. Check pairs of children from start and end moving inward. This generalizes the binary tree symmetry concept.

Result

You can apply symmetry checks beyond binary trees.

Generalizing symmetry broadens your problem-solving skills for diverse tree structures.

Under the Hood

The symmetry check works by recursively or iteratively comparing pairs of nodes from two trees. It verifies if node values match and if the left subtree of one corresponds to the right subtree of the other. This process continues down the tree structure, ensuring every mirrored pair aligns. Internally, recursion uses the call stack to remember node pairs, while iteration uses explicit data structures like queues.

Why designed this way?

This approach was chosen because trees naturally fit recursive definitions, making recursion intuitive and clean. Iterative methods exist to avoid deep recursion limits. The mirror comparison aligns with the mathematical definition of symmetry, ensuring correctness and simplicity.

Start
  │
  ▼
Compare root nodes
  │
  ├─ If both null -> symmetric
  ├─ If one null or values differ -> not symmetric
  └─ Else compare:
       ├─ left subtree of Tree1 with right subtree of Tree2
       └─ right subtree of Tree1 with left subtree of Tree2
  │
  ▼
Repeat recursively or iteratively until all nodes checked

Myth Busters - 3 Common Misconceptions

Quick: do you think two empty trees are not symmetric? Commit to yes or no.

Common Belief: Two empty trees are not symmetric because they have no nodes.

Reality: Two empty trees are symmetric by definition since they mirror each other perfectly with no nodes.

Why it matters: Misunderstanding this leads to incorrect results in base cases and can cause bugs in recursive functions.

Quick: do you think symmetry means trees must be identical? Commit to yes or no.

Common Belief: Symmetric trees must be exactly the same in structure and node order.

Reality: Symmetry means one tree is the mirror image of the other, not identical in left-to-right order.

Why it matters: Confusing symmetry with equality causes wrong conclusions and missed mirror patterns.

Quick: do you think recursion is always safe for symmetry checks? Commit to yes or no.

Common Belief: Recursion is always the best way to check tree symmetry.

Reality: Recursion can cause stack overflow on very deep trees; iterative methods are safer in production.

Why it matters: Ignoring this can cause crashes or performance issues in real-world applications.

Expert Zone

1

Symmetry checks can be combined with subtree checks to detect mirrored subtrees efficiently.

2

Iterative symmetry checks require careful pairing of nodes to avoid missing asymmetries.

3

In some languages, tail recursion optimization can make recursive symmetry checks as efficient as iterative ones.

When NOT to use

Avoid symmetry checks when trees are very large and deep without tail recursion optimization; use iterative methods instead. For non-tree data, other structural comparisons like graph isomorphism are more appropriate.

Production Patterns

Symmetry checks are used in graphics engines to optimize rendering mirrored objects, in compiler design to verify syntax trees, and in network topology validation to ensure balanced routing structures.

Connections

Tree Traversal

Builds-on

Understanding traversal methods is essential because symmetry checks rely on visiting nodes in a mirrored order.

Graph Isomorphism

Related but more general

Symmetry checking is a special case of graph isomorphism where the structure is a tree and the mapping is a mirror.

Human Visual Symmetry Perception

Analogous pattern recognition

Knowing how humans perceive symmetry helps design algorithms that detect mirrored structures efficiently.

Common Pitfalls

#1 Ignoring null checks leading to crashes.

Wrong approach:

if (root1->val == root2->val) {
checkSymmetry(root1->left, root2->right);
checkSymmetry(root1->right, root2->left);
}

Correct approach:

if (root1 == NULL && root2 == NULL) return true;
if (root1 == NULL || root2 == NULL) return false;
if (root1->val != root2->val) return false;
return checkSymmetry(root1->left, root2->right) && checkSymmetry(root1->right, root2->left);

Root cause:

Not handling null pointers before accessing values causes runtime errors.

#2 Comparing nodes in the same position instead of mirrored positions.

Wrong approach:

return checkSymmetry(root1->left, root2->left) && checkSymmetry(root1->right, root2->right);

Correct approach:

return checkSymmetry(root1->left, root2->right) && checkSymmetry(root1->right, root2->left);

Root cause:

Misunderstanding the mirror concept leads to wrong node comparisons.

#3 Using recursion without base case for empty trees.

Wrong approach:

bool checkSymmetry(Node* root1, Node* root2) {
if (root1->val != root2->val) return false;
return checkSymmetry(root1->left, root2->right) && checkSymmetry(root1->right, root2->left);
}

Correct approach:

bool checkSymmetry(Node* root1, Node* root2) {
if (root1 == NULL && root2 == NULL) return true;
if (root1 == NULL || root2 == NULL) return false;
if (root1->val != root2->val) return false;
return checkSymmetry(root1->left, root2->right) && checkSymmetry(root1->right, root2->left);
}

Root cause:

Missing base cases for null nodes causes segmentation faults.

Key Takeaways

Two trees are symmetric if one is the mirror image of the other, matching node values and positions flipped.

Recursion is a natural way to check symmetry by comparing opposite children pairs, but iteration can be safer for deep trees.

Handling edge cases like empty trees and null nodes is critical to avoid errors.

Symmetry checking extends beyond binary trees to more complex structures by comparing children lists in reverse order.

Understanding symmetry helps in many real-world applications like graphics, compilers, and network design.

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