Check if Two Trees are Symmetric in DSA Javascript

Mental Model

Two trees are symmetric if one is a mirror image of the other, meaning their shapes and values match when flipped.

Analogy: Imagine holding two identical tree-shaped paper cutouts. If you flip one over and it fits perfectly on the other, they are symmetric.

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

Dry Run Walkthrough

Input: Tree1: 1 -> 2,3 -> 4,null, null,5; Tree2: 1 -> 3,2 -> 5,null, null,4

Goal: Check if Tree2 is the mirror image of Tree1

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

Tree1 root=1, Tree2 root=1

Why: Roots must be equal for symmetry

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

Tree1 left=2, Tree2 right=2

Why: Mirror nodes must match

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

Tree1 right=3, Tree2 left=3

Why: Mirror nodes must match

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 leaf nodes must match

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 leaf nodes must match

Result:

Trees are symmetric because all corresponding mirror nodes match

Annotated Code

DSA Javascript

class TreeNode {
  constructor(val = 0, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function isSymmetricTrees(t1, t2) {
  if (!t1 && !t2) return true;
  if (!t1 || !t2) return false;
  if (t1.val !== t2.val) return false;
  return isSymmetricTrees(t1.left, t2.right) && isSymmetricTrees(t1.right, t2.left);
}

// Build Tree1
const tree1 = new TreeNode(1,
  new TreeNode(2, new TreeNode(4), null),
  new TreeNode(3, null, new TreeNode(5))
);

// Build Tree2
const tree2 = new TreeNode(1,
  new TreeNode(3, new TreeNode(5), null),
  new TreeNode(2, null, new TreeNode(4))
);

console.log(isSymmetricTrees(tree1, tree2) ? "Trees are symmetric" : "Trees are not symmetric");

if (!t1 && !t2) return true;

both nodes null means symmetry at this branch

if (!t1 || !t2) return false;

one node null and other not means asymmetry

if (t1.val !== t2.val) return false;

node values must match for symmetry

return isSymmetricTrees(t1.left, t2.right) && isSymmetricTrees(t1.right, t2.left);

recursively check mirror children pairs

Output

Trees are symmetric

Complexity Analysis

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

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

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

Edge Cases

Both trees empty

Returns true since empty trees are symmetric

DSA Javascript

if (!t1 && !t2) return true;

One tree empty, other not

Returns false due to asymmetry

DSA Javascript

if (!t1 || !t2) return false;

Trees with different values at mirror nodes

Returns false due to value mismatch

DSA Javascript

if (t1.val !== t2.val) return false;

When to Use This Pattern

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

Common Mistakes

Mistake: Comparing left subtree with left subtree instead of left with right
Fix: Compare t1.left with t2.right and t1.right with t2.left to check mirror symmetry

Summary

Checks if two trees are mirror images by comparing nodes recursively.

Use when you need to verify if one tree is the symmetric mirror of another.

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