Check if Two Trees are Symmetric in DSA Typescript - 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 nodes in a way that the left side of one tree matches the right side of the other, and vice versa. It helps us understand if two tree structures are balanced in a mirrored way. This concept is useful in many areas like graphics, data organization, and algorithms.

Why it matters

Without the ability to check symmetry, programs might fail to recognize balanced or mirrored data structures, leading to errors in processing or visualizing data. Symmetry checks help optimize algorithms that rely on balanced trees, improving performance and correctness. In real life, symmetry is often linked to balance and harmony, so computers use this idea to organize and compare data efficiently.

Where it fits

Before learning this, you should understand basic tree data structures and how to traverse them. After this, you can explore more complex tree algorithms like tree isomorphism, balanced trees, and tree serialization. This topic builds a foundation for understanding how trees relate to each other structurally.

Mental Model

Core Idea

Two trees are symmetric if one is the mirror image of the other, meaning their nodes match when one tree is flipped around its center.

Think of it like...

Imagine holding two identical hand mirrors facing each other. If the reflection in one mirror matches the other exactly but reversed, the two mirrors show symmetric images, just like symmetric trees.

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

Build-Up - 7 Steps

1

Foundation

Understanding Binary Trees Basics

Concept: Introduce what a binary tree is and how nodes connect.

A binary tree is a structure where each node has up to two children: left and right. Each node holds a value. We can move through the tree starting from the root node, visiting children nodes recursively or iteratively.

Result

You can represent data in a tree form where each node branches to two or fewer nodes.

Understanding the basic structure of binary trees is essential before comparing two trees for symmetry.

2

Foundation

Tree Traversal Techniques

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

Common ways to visit nodes include preorder (root-left-right), inorder (left-root-right), and postorder (left-right-root). Traversal helps us access and compare nodes in order.

Result

You can visit every node in a tree in a predictable order.

Knowing traversal methods allows you to compare nodes between two trees effectively.

3

Intermediate

Defining Symmetry Between Two Trees

Concept: Symmetry means one tree is a mirror of the other, so left and right children swap places.

To check symmetry, compare the root nodes of both trees. Then check if the left subtree of the first tree matches the right subtree of the second tree, and vice versa. This comparison continues recursively.

Result

You have a clear rule to decide if two trees are symmetric.

Recognizing that symmetry involves mirrored subtrees guides the recursive comparison approach.

4

Intermediate

Recursive Symmetry Check Implementation

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

Concept: Use recursion to compare nodes in mirrored positions between two 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 node, and right child of first node with left child of second node.

Result

You can determine if two trees are symmetric by recursive calls.

Understanding mirrored recursive calls is key to correctly checking symmetry.

5

Intermediate

Iterative Symmetry Check Using Queue

🤔Before reading on: do you think recursion is the only way to check symmetry, or can iteration work too? Commit to your answer.

Concept: Use a queue to iteratively compare nodes in mirrored positions.

Initialize a queue with the root nodes of both trees. While the queue is 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.

Result

You can check symmetry without recursion, useful for large trees.

Knowing iterative methods helps avoid stack overflow and can be more efficient in some cases.

6

Advanced

Handling Edge Cases and Null Trees

🤔Before reading on: do you think two empty trees are symmetric? What about one empty and one non-empty tree? Commit to your answer.

Concept: Consider cases where trees or subtrees are empty or missing.

Two null trees are symmetric by definition. If one tree is null and the other is not, they are not symmetric. During recursion or iteration, always check for null nodes before comparing values to avoid errors.

Result

Your function correctly handles all tree shapes and sizes.

Accounting for null nodes prevents runtime errors and ensures correctness.

7

Expert

Optimizing Symmetry Checks for Large Trees

🤔Before reading on: do you think checking every node is necessary, or can symmetry be detected early? Commit to your answer.

Concept: Early stopping and pruning improve performance by avoiding unnecessary checks.

If at any point nodes differ, stop checking further. Use short-circuit logic in recursion or iteration. For balanced trees, symmetry check can be done in O(n) time, where n is number of nodes. Avoid redundant comparisons by careful ordering.

Result

Symmetry checks run efficiently even on large trees.

Early detection of asymmetry saves time and resources in real applications.

Under the Hood

The symmetry check works by comparing pairs of nodes from two trees in mirrored positions. Internally, this is a depth-first traversal that simultaneously explores both trees. Each recursive call or iteration compares node values and then proceeds to their children in opposite directions. The call stack or queue maintains pairs of nodes to compare, ensuring all corresponding nodes are checked.

Why designed this way?

This approach leverages the natural recursive structure of trees and the concept of mirror images. Alternatives like flattening trees lose structural information. The mirrored recursive or iterative comparison is simple, intuitive, and efficient, making it a preferred method in many algorithms.

Start
  │
  ▼
Compare root nodes
  │
  ├─ If both null -> symmetric here
  ├─ If one null or values differ -> not symmetric
  │
  ▼
Compare left subtree of Tree1 with right subtree of Tree2
  │
  ▼
Compare right subtree of Tree1 with left subtree of Tree2
  │
  ▼
Repeat recursively or iteratively until all nodes checked

Myth Busters - 3 Common Misconceptions

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

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

Reality: Having the same preorder traversal does not guarantee symmetry because the structure and mirrored positions matter, not just the order of nodes.

Why it matters: Relying on traversal order alone can cause incorrect symmetry checks, leading to wrong algorithm results.

Quick: Do you think symmetry means the trees must be identical? Commit to yes or no.

Common Belief: Symmetric trees are identical trees with the same structure and values.

Reality: Symmetry means one tree is a mirror image of the other, not necessarily identical in left-right order.

Why it matters: Confusing symmetry with identity can cause misunderstanding of tree comparisons and incorrect implementations.

Quick: Do you think checking symmetry requires comparing all nodes even if a mismatch is found early? Commit to yes or no.

Common Belief: You must check every node pair to confirm symmetry.

Reality: You can stop checking as soon as a mismatch is found, saving time.

Why it matters: Not stopping early wastes resources and slows down algorithms unnecessarily.

Expert Zone

1

Symmetry checks can be extended to n-ary trees but require more complex mirrored child comparisons.

2

In some cases, symmetry checking can be combined with subtree hashing to speed up repeated checks.

3

Iterative symmetry checks using queues can be more memory efficient than recursion in deep trees.

When NOT to use

Avoid symmetry checks when tree structure is irrelevant or when only node values matter regardless of position. For unordered trees, use tree isomorphism algorithms instead.

Production Patterns

Symmetry checks are used in graphics engines to optimize rendering of mirrored objects, in compiler design for syntax tree analysis, and in database indexing to verify balanced tree structures.

Connections

Tree Isomorphism

Builds-on

Understanding symmetry helps grasp tree isomorphism, which checks if two trees are structurally identical ignoring node order.

Palindrome Checking

Similar pattern

Both symmetry and palindrome checks involve mirrored comparisons, one in tree structures and the other in sequences.

Human Visual Symmetry Perception

Analogous process

The brain's way of recognizing symmetrical faces or objects parallels how algorithms check mirrored tree structures.

Common Pitfalls

#1 Comparing nodes in the same position instead of mirrored positions.

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:

Misunderstanding that symmetry requires mirrored child comparisons, not same-side comparisons.

#2 Not checking for null nodes before accessing their values.

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:

Ignoring null checks leads to runtime errors when accessing properties of null.

Key Takeaways

Symmetry between two trees means one is the mirror image of the other, not just identical.

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

Handling null nodes carefully is essential to avoid errors and correctly identify symmetry.

Early stopping when a mismatch is found improves efficiency in symmetry checks.

Understanding symmetry lays groundwork for more complex tree comparison algorithms.

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