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.

Practice

1. What does it mean for two binary trees to be symmetric?

easy

A. They are mirror images of each other around their root.

B. They have the same number of nodes.

C. They have the same values in the same order.

D. They are both balanced binary search trees.

Solution

1. Step 1: Understand symmetry in trees

   Two trees are symmetric if one is the mirror reflection of the other around the root node.

2. Step 2: Differentiate from other properties

   Having the same number of nodes or values in order does not guarantee symmetry; symmetry requires mirrored structure and values.

3. Final Answer:

   They are mirror images of each other around their root. -> Option A

4. Quick Check:

   Symmetry means mirror image = A [OK]

Hint: Symmetric trees mirror each other around the root [OK]

Common Mistakes:

• Confusing symmetry with identical trees
• Thinking same node count means symmetry
• Assuming balanced trees are always symmetric

2. Which TypeScript function signature correctly represents a function to check if two trees are symmetric?

easy

A. function symmetricCheck(root1: TreeNode, root2: TreeNode): void

B. function isSymmetric(root1: TreeNode, root2: TreeNode): boolean

C. function checkSymmetry(tree1: TreeNode, tree2: TreeNode): number

D. function isSymmetric(root: TreeNode): boolean

Solution

1. Step 1: Identify correct parameters and return type

   The function should take two tree roots and return a boolean indicating symmetry.

2. Step 2: Check function signature correctness

   function isSymmetric(root1: TreeNode, root2: TreeNode): boolean matches this: two TreeNode parameters and boolean return type.

3. Final Answer:

   function isSymmetric(root1: TreeNode, root2: TreeNode): boolean -> Option B

4. Quick Check:

   Two roots + boolean return = D [OK]

Hint: Symmetry check needs two roots and boolean output [OK]

Common Mistakes:

• Using only one root parameter
• Returning number instead of boolean
• Using void return type

3. What will be the output of the following TypeScript code snippet?

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

function isMirror(t1: TreeNode | null, t2: TreeNode | null): boolean {
  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);
}

const tree1 = new TreeNode(1, new TreeNode(2), new TreeNode(3));
const tree2 = new TreeNode(1, new TreeNode(3), new TreeNode(2));
console.log(isMirror(tree1, tree2));

medium

A. SyntaxError

B. false

C. true

D. RuntimeError

Solution

1. Step 1: Understand the isMirror function logic

   It checks if two trees are mirror images by comparing root values and recursively checking left of one with right of other and vice versa.

2. Step 2: Trace the given trees

   tree1 has root 1, left 2, right 3; tree2 has root 1, left 3, right 2. They are mirrors, so isMirror returns true.

3. Final Answer:

   true -> Option C

4. Quick Check:

   Mirror check returns true for these trees [OK]

Hint: Mirror check compares opposite children recursively [OK]

Common Mistakes:

• Confusing left and right child comparison
• Assuming same structure means mirror
• Ignoring null checks

4. Identify the bug in this TypeScript function meant to check if two trees are symmetric:

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

medium

A. It does not check node values before recursion.

B. It misses the base case when both nodes are null.

C. It returns true when one node is null and the other is not.

D. It compares left with left and right with right instead of mirror sides.

Solution

1. Step 1: Analyze recursive calls

   The function compares t1.left with t2.left and t1.right with t2.right, which checks identical structure, not mirror symmetry.

2. Step 2: Identify correct mirror comparison

   For symmetry, t1.left should be compared with t2.right and t1.right with t2.left.

3. Final Answer:

   It compares left with left and right with right instead of mirror sides. -> Option D

4. Quick Check:

   Mirror needs cross child comparison = A [OK]

Hint: Mirror check swaps left and right children in recursion [OK]

Common Mistakes:

• Comparing same side children instead of opposite
• Forgetting to check node values before recursion
• Missing null base cases

5. Given two binary trees, write a TypeScript function that returns true if they are symmetric around their roots, and false otherwise. Which approach correctly solves this problem?

hard

A. Use a helper function to recursively compare left subtree of one tree with right subtree of the other and vice versa.

B. Traverse both trees in preorder and compare the traversal arrays for equality.

C. Check if both trees have the same height and node count.

D. Compare only the root node values of both trees.

Solution

1. Step 1: Understand symmetry check requirements

   Symmetry means the left subtree of one tree is the mirror of the right subtree of the other.

2. Step 2: Choose correct approach

   Recursively comparing left subtree of one with right subtree of the other ensures mirror symmetry is checked properly.

3. Final Answer:

   Use a helper function to recursively compare left subtree of one tree with right subtree of the other and vice versa. -> Option A

4. Quick Check:

   Mirror recursion approach = B [OK]

Hint: Mirror symmetry needs cross subtree recursive comparison [OK]

Common Mistakes:

• Comparing preorder traversals which miss mirror structure
• Checking only height or node count
• Comparing only root values