Check if Two Trees are Symmetric in DSA Java - 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 subtree of one tree matches the right subtree of the other, and vice versa. It helps us understand if the structure and values of two trees reflect each other perfectly. This concept is important in many tree-related problems and algorithms.

Why it matters

Without the ability to check symmetry between trees, many algorithms that rely on balanced or mirrored structures would fail or become inefficient. Symmetry checks help in optimizing tree operations, validating tree transformations, and solving problems like palindrome trees or graphical reflections. In real life, symmetry is often linked to balance and harmony, and in computing, it helps ensure data structures behave predictably.

Where it fits

Before learning this, you should understand basic tree structures, especially binary trees, and how to traverse them. After mastering symmetry checks, you can explore tree balancing, tree isomorphism, and advanced tree algorithms like AVL or Red-Black trees.

Mental Model

Core Idea

Two trees are symmetric if one is the mirror reflection of the other, meaning their left and right subtrees are swapped but identical in structure and values.

Think of it like...

Imagine holding two identical hand mirrors facing each other. If the image in one mirror matches the reflection in the other perfectly, the two mirrors are symmetric. Similarly, two trees are symmetric if one looks like the mirror image of the other.

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

Symmetry means Tree1's left subtree matches Tree2's right subtree and vice versa.

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. For example, a node with value 1 can have a left child with value 2 and a right child with value 3. Trees grow by connecting nodes this way.

Result

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

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

2

Foundation

Learn Tree Traversal Basics

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

Traversal means visiting all nodes in a tree in a specific order. Common ways are preorder (node, left, right), inorder (left, node, right), and postorder (left, right, node). Traversal helps us access and compare nodes.

Result

You can write code to visit every node in a tree and process its value.

Traversal is the tool that lets us compare nodes between two trees step-by-step.

3

Intermediate

Define Symmetry Between Two Trees

Concept: Understand what it means for two trees to be mirror images in terms of node values and structure.

Two trees are symmetric if the left subtree of one matches the right subtree of the other, and the right subtree of one matches the left subtree of the other. This means for every node pair, their values must be equal, and their children must be symmetric in swapped positions.

Result

You can describe symmetry as a recursive condition comparing swapped children.

Knowing symmetry is about mirrored subtrees guides how to compare nodes recursively.

4

Intermediate

Implement Recursive Symmetry Check

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

Concept: Use recursion to compare nodes in swapped positions to verify symmetry.

Write a function that takes two nodes. If both are null, they are symmetric. If one is null and the other isn't, not symmetric. If values differ, not symmetric. 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

The function returns true if all corresponding nodes match in mirrored positions, false otherwise.

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

5

Intermediate

Handle Edge Cases in Symmetry

🤔Before reading on: do you think two empty trees are symmetric? Commit to yes or no.

Concept: Consider cases like empty trees, single-node trees, and unbalanced trees.

Two empty trees are symmetric by definition. A single-node tree is symmetric with itself. If one tree is empty and the other is not, they are not symmetric. Unbalanced trees with different shapes cannot be symmetric.

Result

Your symmetry check correctly handles all these special cases without errors.

Handling edge cases prevents bugs and ensures your function works for all inputs.

6

Advanced

Optimize Symmetry Check with Iteration

🤔Before reading on: do you think recursion is the only way to check symmetry? Commit to yes or no.

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

Instead of recursion, use a queue to store pairs of nodes to compare. Start by enqueueing the root nodes of both trees. While the queue is not empty, dequeue a pair, compare values, and enqueue their children in swapped order. If any mismatch occurs, return false. If all pairs match, return true.

Result

You get the same result as recursion but avoid potential stack overflow on deep trees.

Iteration can replace recursion to improve performance and handle very deep trees safely.

7

Expert

Understand Symmetry in Tree Isomorphism

🤔Before reading on: do you think symmetry is the same as tree isomorphism? Commit to yes or no.

Concept: Symmetry is a special case of tree isomorphism where one tree is the mirror of the other.

Tree isomorphism checks if two trees have the same shape and node values, possibly after rearranging children. Symmetry specifically requires the rearrangement to be a mirror swap of left and right children. This subtle difference means symmetry checks are simpler but more specific than general isomorphism.

Result

You understand that symmetry checking is a focused form of comparing tree structures.

Knowing symmetry's relation to isomorphism helps in solving broader tree comparison problems.

Under the Hood

The symmetry check works by recursively or iteratively comparing pairs of nodes from two trees. At each step, it verifies if the current nodes have equal values and if their children are mirrors: left child of one matches right child of the other and vice versa. This process continues down the tree levels until all nodes are checked or a mismatch is found.

Why designed this way?

This approach leverages the natural recursive structure of trees, making the code simple and elegant. It avoids unnecessary comparisons by focusing only on mirrored pairs. Alternatives like flattening trees or comparing traversals are less efficient or more complex. The design balances clarity, correctness, and performance.

Start
  │
  ▼
Compare root nodes
  │
  ├─ If both null -> symmetric
  ├─ If one null -> not symmetric
  ├─ If values differ -> not symmetric
  └─ Else
       │
       ├─ Recursively compare left of Tree1 with right of Tree2
       └─ Recursively compare right of Tree1 with left of Tree2
  │
  ▼
Repeat until leaves
  │
  ▼
Return true if all pairs symmetric

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 visited nodes.

Why it matters: Relying on traversal equality alone can cause incorrect assumptions about symmetry, 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 node values in the same positions.

Reality: Symmetry means one tree is the mirror image of the other, so their structures are mirrored, not identical in layout.

Why it matters: Confusing symmetry with identity can cause wrong comparisons and missed opportunities to detect mirrored structures.

Quick: do you think an empty tree is symmetric with a non-empty tree? Commit to yes or no.

Common Belief: An empty tree can be 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 false positives in symmetry checks and bugs in tree algorithms.

Expert Zone

1

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

2

In some applications, node values may be ignored, and only structure symmetry is checked, which changes the comparison criteria.

3

Iterative symmetry checks can be optimized using double-ended queues to reduce memory overhead.

When NOT to use

Avoid symmetry checks when trees are large and unbalanced with no expected mirrored structure; instead, use general tree comparison or hashing techniques. For trees with more than two children per node, specialized algorithms are needed.

Production Patterns

Symmetry checks are used in graphical applications to detect mirrored shapes, in compiler design to optimize abstract syntax trees, and in database indexing to verify balanced tree structures.

Connections

Tree Isomorphism

Symmetry checking is a special case of tree isomorphism where the mapping is a mirror reflection.

Understanding symmetry helps grasp the broader concept of tree isomorphism and structural equivalence.

Palindrome Strings

Symmetry in trees is conceptually similar to palindromes in strings, where the sequence reads the same forwards and backwards.

Recognizing this connection aids in transferring recursive and iterative techniques between string and tree problems.

Mirror Symmetry in Physics

Mirror symmetry in trees parallels physical mirror symmetry where objects are reflected across a plane.

This cross-domain link shows how symmetry principles unify concepts in computer science and natural sciences.

Common Pitfalls

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

Wrong approach:

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

Correct approach:

boolean isSymmetric(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return true;
if (t1 == null || t2 == null) 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 handling null nodes properly leading to NullPointerException.

Wrong approach:

if (t1.val != t2.val) return false;
// no null checks before accessing val

Correct approach:

if (t1 == null && t2 == null) return true;
if (t1 == null || t2 == null) return false;
if (t1.val != t2.val) return false;

Root cause:

Forgetting to check for null before accessing node values causes runtime errors.

#3 Assuming two empty trees are not symmetric.

Wrong approach:

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

Correct approach:

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

Root cause:

Confusing null checks and not recognizing that two null trees are symmetric.

Key Takeaways

Symmetry between two trees means one is the mirror image of the other, with left and right children swapped but matching in value and structure.

Recursive and iterative approaches both work for symmetry checks, but recursion naturally fits the problem's mirrored structure.

Handling edge cases like empty trees and null nodes is crucial to avoid errors and incorrect results.

Symmetry checking is a special case of tree isomorphism and relates conceptually to palindromes and mirror symmetry in other fields.

Common mistakes include comparing nodes in the same position instead of mirrored positions and not properly handling null nodes.

Practice

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

easy

A. They have identical left subtrees only.

B. They have the same number of nodes.

C. They are mirror images of each other around their center.

D. They have the same root value 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 = D [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 Java method signature correctly defines a function to check if two trees are symmetric?

easy

A. public boolean isSymmetric(TreeNode root1, TreeNode root2)

B. boolean isSymmetric(TreeNode root1, TreeNode root2) {}

C. public void isSymmetric(TreeNode root1, TreeNode root2)

D. public boolean isSymmetric(TreeNode root)

Solution

1. Step 1: Identify correct return type and parameters

   The method should return boolean and accept two TreeNode parameters for two trees.

2. Step 2: Check method signature syntax

   Public access, boolean return, and parameter types match in public boolean isSymmetric(TreeNode root1, TreeNode root2).

3. Final Answer:

   public boolean isSymmetric(TreeNode root1, TreeNode root2) -> Option A

4. Quick Check:

   Correct signature returns boolean with two TreeNode inputs [OK]

Hint: Boolean return with two TreeNode inputs is needed [OK]

Common Mistakes:

• Using void return type
• Missing public keyword
• Using only one TreeNode parameter

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

TreeNode root1 = new TreeNode(1);
root1.left = new TreeNode(2);
root1.right = new TreeNode(3);
TreeNode root2 = new TreeNode(1);
root2.left = new TreeNode(3);
root2.right = new TreeNode(2);

System.out.println(isSymmetric(root1, root2));

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

medium

A. Runtime exception

B. false

C. Compilation error

D. true

Solution

1. Step 1: Analyze tree structure and values

   root1 has left=2, right=3; root2 has left=3, right=2, which are mirror images.

2. Step 2: Trace recursive calls

   Values match and recursive calls check mirrored children, all return true.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Mirror structure and values = true [OK]

Hint: Check mirrored nodes and values recursively [OK]

Common Mistakes:

• Ignoring mirrored child comparison
• Confusing left and right children
• Assuming same structure means false

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

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

medium

A. It compares left with left and right with right instead of mirrored children.

B. It does not check for null nodes.

C. It returns true when both nodes are null.

D. It uses incorrect return type.

Solution

1. Step 1: Review recursive calls for symmetry

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

2. Step 2: Identify correct mirrored comparison

   It should compare t1.left with t2.right and t1.right with t2.left for symmetry.

3. Final Answer:

   It compares left with left and right with right instead of mirrored children. -> Option A

4. Quick Check:

   Mirror check needs cross child comparison [OK]

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

Common Mistakes:

• Comparing same side children instead of mirrored
• Ignoring null checks
• Wrong return type usage

5. Given two binary trees, write a Java method to check if they are symmetric. Which approach correctly solves this problem? A) Traverse both trees in preorder and compare node values in order. B) Recursively check if left subtree of first tree is mirror of right subtree of second tree and vice versa. C) Compare the height of both trees and return true if equal. D) Check if both trees have the same number of leaf nodes.

hard

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

B. Recursively check if left subtree of first tree is mirror of right subtree of second tree and vice versa.

C. Compare the height of both trees and return true if equal.

D. Check if both trees have the same number of leaf nodes.

Solution

1. Step 1: Understand symmetry check requirements

   Symmetry means one tree is mirror image of the other, so left subtree of one matches right subtree of other.

2. Step 2: Evaluate approaches

   Recursively check if left subtree of first tree is mirror of right subtree of second tree and vice versa. correctly uses recursive mirror checks; others ignore structure or order.

3. Final Answer:

   Recursively check if left subtree of first tree is mirror of right subtree of second tree and vice versa. -> Option B

4. Quick Check:

   Mirror recursive check solves symmetry [OK]

Hint: Mirror recursive check is key to symmetry [OK]

Common Mistakes:

• Using preorder traversal comparison
• Comparing only height or leaf counts
• Ignoring mirrored subtree checks