Check if Two Trees are Symmetric in DSA C++

Mental Model

Two trees are symmetric if one is a mirror image of the other. We compare nodes in a way that matches left of one tree to right of the other.

Analogy: Imagine two people standing face to face holding hands. Their left and right hands match perfectly as mirror images. If one raises left hand, the other raises right hand at the same height.

Tree1:       1           Tree2:       1
           /   \                   /   \
          2     3                 3     2
         /       \               /       \
        4         5             5         4

Pointers: ↑ compare Tree1 left subtree with Tree2 right subtree

Dry Run Walkthrough

Input: Tree1: 1->2,3->4,null,5,null; Tree2: 1->1,3->3,null,5,null (mirror structure with values 1,2,3,4,5 and 1,3,2,5,4)

Goal: Check if Tree1 and Tree2 are mirror images (symmetric) in structure and values

Step 1: Compare root nodes of both trees (1 and 1)

Tree1 root=1, Tree2 root=1

Why: Roots must be equal to start symmetry check

Step 2: Compare left child of Tree1 (2) with right child of Tree2 (2)

Tree1 left=2, Tree2 right=2

Why: Left subtree of one matches right subtree of other for symmetry

Step 3: Compare right child of Tree1 (3) with left child of Tree2 (3)

Tree1 right=3, Tree2 left=3

Why: Right subtree of one matches left subtree of other for symmetry

Step 4: Compare left child of Tree1's left node (4) with right child of Tree2's right node (4)

Tree1 left.left=4, Tree2 right.right=4

Why: Mirror children must match in value and position

Step 5: Compare right child of Tree1's right node (5) with left child of Tree2's left node (5)

Tree1 right.right=5, Tree2 left.left=5

Why: Mirror children must match in value and position

Step 6: No more children to compare, all matched

All corresponding nodes matched symmetrically

Why: All pairs matched, trees are symmetric

Result:

Symmetric: true

Annotated Code

DSA C++

#include <iostream>
using namespace std;

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; // both null means symmetric
    if (!t1 || !t2) return false; // one null means not symmetric
    if (t1->val != t2->val) return false; // values must match
    // check left of t1 with right of t2 and right of t1 with left of t2
    return isMirror(t1->left, t2->right) && isMirror(t1->right, t2->left);
}

bool areSymmetricTrees(TreeNode* root1, TreeNode* root2) {
    return isMirror(root1, root2);
}

int main() {
    // Construct Tree1
    TreeNode* root1 = new TreeNode(1);
    root1->left = new TreeNode(2);
    root1->right = new TreeNode(3);
    root1->left->left = new TreeNode(4);
    root1->right->right = new TreeNode(5);

    // Construct Tree2 (mirror of Tree1)
    TreeNode* root2 = new TreeNode(1);
    root2->left = new TreeNode(3);
    root2->right = new TreeNode(2);
    root2->left->left = new TreeNode(5);
    root2->right->right = new TreeNode(4);

    bool result = areSymmetricTrees(root1, root2);
    cout << (result ? "Symmetric: true" : "Symmetric: false") << endl;

    return 0;
}

if (!t1 && !t2) return true; // both null means symmetric

base case: both nodes null means symmetry at this branch

if (!t1 || !t2) return false; // one null means not symmetric

if one node is null and other not, symmetry breaks

if (t1->val != t2->val) return false; // values must match

node values must be equal for symmetry

return isMirror(t1->left, t2->right) && isMirror(t1->right, t2->left);

recursively check left subtree of one with right subtree of other and vice versa

Output

Symmetric: true

Complexity Analysis

Time: O(n) because we visit each node once to compare both trees

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Compared to flattening trees to arrays and reversing one, this uses less space and is more direct

Edge Cases

Both trees are empty (null)

Returns true because empty trees are symmetric

DSA C++

if (!t1 && !t2) return true; // both null means symmetric

One tree is empty, other is not

Returns false because symmetry breaks

DSA C++

if (!t1 || !t2) return false; // one null means not symmetric

Trees have same structure but different node values

Returns false because values differ

DSA C++

if (t1->val != t2->val) return false; // values must match

When to Use This Pattern

When asked if two trees are mirror images or symmetric, use a recursive check comparing left subtree of one with right subtree of the other.

Common Mistakes

Mistake: Comparing left subtree with left subtree and right with right instead of cross comparison
Fix: Compare left subtree of first tree with right subtree of second tree and vice versa

Mistake: Not checking for null nodes before accessing values
Fix: Add base cases to handle null nodes before value comparison

Summary

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

Use when you need to verify if two trees are symmetric in structure and values.

The key is to compare left subtree of one tree with right subtree of the other and vice versa.

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