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.