Check if Two Trees are Symmetric in DSA Typescript

Mental Model

Two trees are symmetric if one is a mirror image of the other, meaning their shapes and node 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                         4

Dry Run Walkthrough

Input: Tree1: 1 -> 2 -> 4 (left subtree), 1 -> 3 (right subtree); Tree2: 1 -> 3 -> 4 (left subtree), 1 -> 2 (right subtree)

Goal: Check if Tree2 is the mirror image of Tree1

Step 1: Compare roots 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 means left of one equals right of other

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

Tree1 right=3, Tree2 left=3

Why: Mirror means right of one equals left of other

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

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

Why: One side has node, other side null means not symmetric here

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

Both null

Why: Both null means symmetric at this branch

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

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

Why: Mismatch: one null, other node means not symmetric

Result:

Trees are not symmetric because some mirrored nodes do not match in structure or value.

Annotated Code

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

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

// Driver code to test
const tree1 = new TreeNode(1,
  new TreeNode(2, new TreeNode(4), null),
  new TreeNode(3)
);
const tree2 = new TreeNode(1,
  new TreeNode(3, null, new TreeNode(4)),
  new TreeNode(2)
);

console.log(isSymmetricTrees(tree1, tree2));

if (t1 === null && t2 === null) return true;

both nodes null means symmetric at this branch

if (t1 === null || t2 === null) return false;

one node null and other not means not symmetric

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 left subtree of one with right subtree of other and vice versa

Output

false

Complexity Analysis

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

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

vs Alternative: Compared to flattening trees to arrays and comparing, this uses less space and is faster by checking structure directly

Edge Cases

Both trees are empty (null)

Returns true because empty trees are symmetric

DSA Typescript

if (t1 === null && t2 === null) return true;

One tree is empty, other is not

Returns false because structure differs

DSA Typescript

if (t1 === null || t2 === null) return false;

Trees have same structure but different node values

Returns false due to value mismatch

DSA Typescript

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

When to Use This Pattern

When asked if two trees are mirror images or symmetric, 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 and their mirrored children.

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

The key is to compare left subtree of one tree with right subtree of the other recursively.