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.

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 = C [OK]

Hint: Symmetric trees mirror each other exactly [OK]

Common Mistakes:

• Thinking same number of nodes means symmetric
• Only comparing root values
• Ignoring structure differences

2. Which of the following is the correct JavaScript function signature to check if two trees are symmetric?

easy

A. function checkSymmetric(tree) {}

B. function isSymmetric(tree1, tree2) {}

C. function symmetricCheck(tree1, tree2, tree3) {}

D. function isSymmetric(tree1) {}

Solution

1. Step 1: Identify parameters needed

   To check symmetry between two trees, we need two tree inputs.

2. Step 2: Match function signature

   Only the function with two parameters for two trees matches the requirement.

3. Final Answer:

   function isSymmetric(tree1, tree2) {} -> Option B

4. Quick Check:

   Two trees need two parameters = B [OK]

Hint: Two trees need two parameters in function [OK]

Common Mistakes:

• Using only one tree parameter
• Adding unnecessary third parameter
• Wrong function naming

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

function isMirror(t1, 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);
}

const tree1 = { val: 1, left: { val: 2, left: null, right: null }, right: { val: 3, left: null, right: null } };
const tree2 = { val: 1, left: { val: 3, left: null, right: null }, right: { val: 2, left: null, right: null } };

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

medium

A. TypeError

B. false

C. undefined

D. true

Solution

1. Step 1: Check base cases for null nodes

   Both trees have matching null nodes at corresponding mirror positions, so base cases return true.

2. Step 2: Compare node values and recursive calls

   Root values match (1), left of tree1 (2) matches right of tree2 (2), right of tree1 (3) matches left of tree2 (3). All recursive calls return true.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Mirror check returns true for symmetric trees [OK]

Hint: Mirror check compares opposite children recursively [OK]

Common Mistakes:

• Confusing left and right children in recursion
• Ignoring null node base cases
• Assuming order of children doesn't matter

4. Identify the bug in this code snippet that checks if two trees are symmetric:

function isMirror(t1, 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 compares left with left and right with right instead of mirror sides.

B. It does not check for null nodes.

C. It uses assignment instead of comparison.

D. It returns true too early without recursion.

Solution

1. Step 1: Analyze recursive calls for symmetry

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

2. Step 2: Correct recursive calls for mirror check

   To check 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 A

4. Quick Check:

   Mirror check swaps sides in recursion = A [OK]

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

Common Mistakes:

• Comparing same sides instead of mirror sides
• Missing null checks
• Using assignment (=) instead of equality (===)

5. Given two binary trees, write a function to check if they are symmetric. Which approach correctly solves this problem?

hard

A. Use a queue to iteratively compare nodes from left of one tree and right of the other.

B. Compare only the root nodes of both trees.

C. Check if both trees have the same height only.

D. Traverse both trees in preorder and compare node values in order.

Solution

1. Step 1: Understand iterative symmetry check

   Using a queue, we can compare nodes from the left side of one tree with the right side of the other tree iteratively.

2. Step 2: Why other methods fail

   Preorder traversal compares nodes in the same order, not mirror order. Height check or root-only check ignores structure and values.

3. Final Answer:

   Use a queue to iteratively compare nodes from left of one tree and right of the other. -> Option A

4. Quick Check:

   Iterative mirror check uses queue swapping sides = D [OK]

Hint: Use queue to compare opposite sides iteratively [OK]

Common Mistakes:

• Using preorder traversal without mirroring
• Checking only height or root values
• Ignoring iterative approach benefits