Check if Two Trees are Symmetric in DSA Javascript - Deep Dive

Overview - Check if Two Trees are Symmetric

What is it?

Checking if two trees are symmetric means verifying if one tree is a mirror image of the other. This involves comparing the structure and values of nodes in both trees to see if they match in a mirrored way. If every left child in one tree matches the right child in the other, and vice versa, the trees are symmetric. This concept helps understand tree structures and their relationships.

Why it matters

Without this concept, we would struggle to compare tree-like data structures that represent mirrored or balanced information. Many real-world problems, like checking palindromes in trees or validating symmetric designs, rely on this. Without symmetry checks, algorithms could miss errors or inefficiencies in data organization, leading to bugs or poor performance.

Where it fits

Before learning this, you should understand basic tree structures, especially binary trees, and how to traverse them. After this, you can explore more complex tree algorithms like tree isomorphism, subtree checks, or balanced tree validations.

Mental Model

Core Idea

Two trees are symmetric if one is the mirror reflection of the other in both structure and node values.

Think of it like...

Imagine two hands facing each other palm to palm. If every finger on the left hand matches the corresponding finger on the right hand but reversed, the hands are symmetric.

Tree1:           Tree2 (mirror)
    1                 1
   / \               / \
  2   3             3   2
 /                   \
4                     4

Build-Up - 7 Steps

1

Foundation

Understand Binary Tree Structure

Concept: Learn what a binary tree is and how nodes connect with left and right children.

A binary tree is a structure where each node has up to two children: left and right. Each node holds a value. Trees start from a root node and branch out. For example, a node with value 1 can have left child 2 and right child 3.

Result

You can visualize and represent trees with nodes and their left/right links.

Understanding the basic tree structure is essential because symmetry depends on comparing these left and right branches.

2

Foundation

Learn Tree Traversal Basics

Concept: Explore how to visit nodes in a tree systematically.

Traversal means visiting all nodes in a tree. Common ways are preorder (root-left-right), inorder (left-root-right), and postorder (left-right-root). Traversal helps us compare nodes between trees.

Result

You can write code to visit every node in a tree in a specific order.

Traversal is the tool that lets us check nodes one by one to compare two trees.

3

Intermediate

Define Symmetry in Trees

Concept: Symmetry means one tree is a mirror image of the other in structure and values.

Two trees are symmetric if the left subtree of one matches the right subtree of the other, and vice versa. This means node values must be equal and their children must be symmetric in opposite positions.

Result

You can describe symmetry as a recursive comparison of opposite children.

Seeing symmetry as mirrored subtrees helps break down the problem into smaller, similar checks.

4

Intermediate

Implement Recursive Symmetry Check

🤔Before reading on: do you think checking symmetry requires comparing nodes in the same position or opposite positions? Commit to your answer.

Concept: Use recursion to compare nodes in opposite positions in both trees.

Write a function that takes two nodes. If both are null, they match. If one is null or values differ, they don't. Otherwise, recursively check left child of first node with right child of second, and right child of first with left child of second.

Result

The function returns true if all mirrored pairs match, false otherwise.

Recursion naturally fits symmetry because it breaks the problem into smaller mirrored parts.

5

Intermediate

Handle Edge Cases in Symmetry

🤔Before reading on: do you think empty trees are symmetric? Commit to your answer.

Concept: Consider cases like empty trees, single-node trees, and trees with missing children.

Empty trees are symmetric by definition. A single-node tree is symmetric with itself. If one subtree is missing but the other isn't, trees are not symmetric. These cases must be handled explicitly in code.

Result

Your function correctly returns true or false for all edge cases.

Handling edge cases prevents bugs and ensures your symmetry check is robust.

6

Advanced

Optimize Symmetry Check with Iteration

🤔Before reading on: do you think recursion is the only way to check symmetry? Commit to your answer.

Concept: Use a queue or stack to iteratively compare nodes instead of recursion.

Initialize a queue with the root nodes of both trees. While queue not empty, dequeue two nodes and compare. If both null, continue. If one null or values differ, return false. Enqueue children in mirrored order: left of first with right of second, right of first with left of second. Continue until queue empty.

Result

The iterative method returns true if trees are symmetric, false otherwise.

Iteration avoids call stack limits and can be easier to debug in large trees.

7

Expert

Understand Symmetry in Non-Binary Trees

🤔Before reading on: do you think symmetry checking applies only to binary trees? Commit to your answer.

Concept: Extend symmetry concepts to trees with more than two children per node.

For trees with multiple children, symmetry means the list of children in one tree is the reverse of the other, and each corresponding child pair is symmetric. This requires comparing children lists from opposite ends recursively.

Result

You can check symmetry in general trees, not just binary ones.

Recognizing symmetry beyond binary trees broadens the concept's application in complex data structures.

Under the Hood

The symmetry check works by recursively or iteratively comparing pairs of nodes from two trees in opposite positions. Each comparison verifies node values and then proceeds to their children in mirrored order. This process uses the call stack or an explicit queue/stack to track pairs to compare. The algorithm stops early if any mismatch is found, ensuring efficiency.

Why designed this way?

This approach leverages the natural recursive structure of trees and the concept of mirror images. Alternatives like flattening trees or comparing traversals fail to capture structural symmetry fully. The recursive or iterative paired comparison ensures both structure and values are checked simultaneously, which is essential for correctness.

Start
  │
  ▼
Compare root nodes
  │
  ├─ If both null -> symmetric
  ├─ If one null or values differ -> not symmetric
  └─ Else compare children pairs:
       ├─ left of Tree1 with right of Tree2
       └─ right of Tree1 with left of Tree2
  │
  ▼
Repeat recursively or iteratively until all pairs checked

Myth Busters - 4 Common Misconceptions

Quick: Do two trees with the same preorder traversal always mean they are symmetric? Commit to yes or no.

Common Belief: If two trees have the same preorder traversal, they must be symmetric.

Reality: Same preorder traversal does not guarantee symmetry because preorder does not capture mirrored structure.

Why it matters: Relying on traversal alone can cause false positives, leading to incorrect assumptions about tree symmetry.

Quick: Is an empty tree symmetric with a non-empty tree? Commit to yes or no.

Common Belief: An empty tree is symmetric with any tree because it has no nodes to compare.

Reality: An empty tree is only symmetric with another empty tree; any non-empty tree is not symmetric with an empty one.

Why it matters: Ignoring this leads to wrong results when checking symmetry involving empty trees.

Quick: Do you think symmetry checking requires trees to have the same number of nodes? Commit to yes or no.

Common Belief: Trees with different numbers of nodes can still be symmetric.

Reality: Symmetric trees must have the same number of nodes arranged in mirrored positions.

Why it matters: Failing to check node counts can cause incorrect symmetry detection.

Quick: Can symmetry checking be done without comparing node values? Commit to yes or no.

Common Belief: Only the structure matters; node values don't affect symmetry.

Reality: Both structure and node values must match in mirrored positions for trees to be symmetric.

Why it matters: Ignoring node values can falsely mark trees as symmetric when they differ in content.

Expert Zone

1

Symmetry checking can be combined with subtree pruning to optimize large tree comparisons by skipping identical subtrees.

2

In iterative symmetry checks, the order of enqueuing children pairs is critical; reversing this breaks correctness.

3

Symmetry concepts extend to graph isomorphism problems when restricted to tree-like graphs, revealing deeper algorithmic connections.

When NOT to use

Avoid symmetry checks when trees are unordered or when only structural similarity (not mirrored) is needed. Use tree isomorphism or subtree matching algorithms instead.

Production Patterns

Symmetry checks appear in UI layout validations, compiler syntax tree optimizations, and palindrome tree problems in coding interviews.

Connections

Palindrome Checking

Symmetry in trees is a structural form of palindrome in sequences.

Understanding tree symmetry deepens insight into palindrome patterns beyond strings, showing how mirrored structures appear in data.

Graph Isomorphism

Symmetry checking is a special case of graph isomorphism where one graph is the mirror of the other.

Knowing symmetry helps grasp more complex graph matching problems by focusing on mirrored node correspondences.

Human Anatomy

Human body symmetry mirrors the concept of tree symmetry in biology.

Recognizing symmetry in nature helps appreciate why algorithms check mirrored structures for balance and correctness.

Common Pitfalls

#1 Confusing symmetry with equality of trees.

Wrong approach:

function isSymmetric(t1, t2) {
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);
}

Correct approach:

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

Root cause:

Mixing up mirrored child comparisons with same-side child comparisons causes wrong results.

#2 Not handling null nodes properly.

Wrong approach:

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

Correct approach:

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

Root cause:

Skipping null checks leads to runtime errors or incorrect symmetry results.

#3 Using preorder traversal comparison for symmetry.

Wrong approach:

function isSymmetric(t1, t2) {
return preorder(t1) === preorder(t2);
}
function preorder(node) {
if (!node) return '#';
return node.val + preorder(node.left) + preorder(node.right);
}

Correct approach:

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

Root cause:

Traversal strings do not capture mirrored structure, so this approach fails.

Key Takeaways

Symmetry in trees means one tree is the mirror image of the other in both structure and node values.

Checking symmetry requires comparing nodes in opposite positions recursively or iteratively.

Handling edge cases like empty trees and null children is essential for correct symmetry checks.

Symmetry concepts extend beyond binary trees and connect to broader problems like palindrome detection and graph isomorphism.

Common mistakes include confusing symmetry with equality and ignoring null checks, which lead to incorrect results.

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