Check if Two Trees are Symmetric in DSA Python - 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 two trees have the same shape and values but flipped. This concept is useful in many tree-related problems and algorithms.

Why it matters

Without this concept, we would struggle to quickly determine if two trees are mirror images, which is important in tasks like validating symmetric data structures or graphical representations. It helps in optimizing algorithms that rely on tree symmetry, saving time and resources. In real life, symmetry checks can be used in image processing, network design, and more.

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 problems like tree isomorphism, subtree checks, and balanced trees.

Mental Model

Core Idea

Two trees are symmetric if the left subtree of one is the mirror reflection of the right subtree of the other, and their node values match.

Think of it like...

Imagine two hands facing each other with palms open. If you fold one hand over the other, they should match perfectly in shape and finger positions. The trees are symmetric if they fit like these two hands mirrored.

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

Check if left of Tree1 matches right of Tree2 and vice versa.

Build-Up - 6 Steps

1

Foundation

Understanding Binary Trees Basics

Concept: Learn what a binary tree is and how nodes connect as 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 root node with value 1 can have a left child 2 and right child 3. This structure forms the basis for symmetry checks.

Result

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

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

2

Foundation

Tree Traversal Techniques

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

Common traversals include preorder (root-left-right), inorder (left-root-right), and postorder (left-right-root). For symmetry, we often use a modified traversal that compares nodes in a mirrored way.

Result

You can visit and process all nodes in a tree in a specific order.

Knowing traversal methods helps you understand how to compare nodes in two trees step-by-step.

3

Intermediate

Defining Symmetry Between Two Trees

🤔Before reading on: do you think two trees are symmetric if their root values differ? Commit to yes or no.

Concept: Symmetry means the root values must be the same, and the left subtree of one tree must mirror the right subtree of the other.

To check symmetry, start at the roots. If roots differ, trees are not symmetric. Then recursively check if left child of Tree1 matches right child of Tree2 and right child of Tree1 matches left child of Tree2.

Result

You can decide if two trees are mirror images by comparing nodes recursively.

Understanding that symmetry requires matching root values and mirrored subtrees is key to building the checking algorithm.

4

Intermediate

Recursive Symmetry Check Algorithm

🤔Before reading on: do you think an iterative approach is simpler than recursion for symmetry? Commit to your answer.

Concept: Use recursion to compare nodes pairwise, moving inward from the roots to leaves.

Define a function that takes two nodes. If both are null, return True. If one is null or values differ, return False. Otherwise, recursively check left of first node with right of second node and right of first node with left of second node.

Result

A clear, concise method to check symmetry using recursion.

Recursion naturally fits the problem because symmetry is a mirrored, repeated pattern down the tree.

5

Advanced

Iterative Symmetry Check Using Queue

🤔Before reading on: do you think using a queue can replace recursion for symmetry checks? Commit to yes or no.

Concept: Use a queue to iteratively compare nodes in pairs, simulating the recursive approach.

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

An iterative method that avoids recursion stack limits and achieves the same result.

Knowing iterative alternatives helps handle large trees where recursion might cause stack overflow.

6

Expert

Handling Edge Cases and Performance

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

Concept: Consider empty trees, trees with different shapes, and optimize for early exits.

Empty trees are symmetric by definition. If one tree is empty and the other is not, they are not symmetric. Also, stop checking as soon as a mismatch is found to save time. For very large trees, iterative approach may be preferred to avoid recursion depth issues.

Result

Robust symmetry check that handles all cases efficiently.

Handling edge cases prevents bugs and improves reliability in real-world applications.

Under the Hood

The symmetry check works by comparing pairs of nodes from two trees in a mirrored fashion. Internally, the algorithm either uses recursion or a queue to traverse nodes simultaneously. Each comparison checks if node values match and if their children are mirrors. This process continues until all nodes are checked or a mismatch is found.

Why designed this way?

This approach leverages the natural recursive structure of trees and the concept of mirror reflection. Alternatives like flattening trees or comparing traversals are less direct and less efficient. The recursive or iterative paired comparison is simple, elegant, and efficient.

┌─────────────┐       ┌─────────────┐
│   Tree1     │       │   Tree2     │
│    Root     │       │    Root     │
└─────┬───────┘       └─────┬───────┘
      │                     │
┌─────┴───────┐       ┌─────┴───────┐
│ Left Child  │       │ Right Child │
│  (Node A)   │       │  (Node B)   │
└─────┬───────┘       └─────┬───────┘
      │                     │
Compare Node A with Node B recursively
(similar for right child of Tree1 and left child of Tree2)

Myth Busters - 3 Common Misconceptions

Quick: do you think two empty trees are not symmetric? Commit to yes or no.

Common Belief: Two empty trees are not symmetric because they have no nodes to compare.

Reality: Two empty trees are symmetric by definition since they mirror each other perfectly with no nodes.

Why it matters: Misunderstanding this leads to incorrect results when checking trees that might be empty, causing false negatives.

Quick: do you think 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: Same preorder traversal does not guarantee symmetry because the structure and mirrored positions matter, not just node order.

Why it matters: Relying on traversal alone can cause wrong symmetry checks, missing structural differences.

Quick: do you think symmetry means identical trees? Commit to yes or no.

Common Belief: Symmetric trees must be identical in structure and node positions.

Reality: Symmetry means mirror images, not identical. The left subtree of one matches the right subtree of the other, flipped.

Why it matters: Confusing symmetry with identity leads to rejecting valid symmetric trees and misunderstanding the problem.

Expert Zone

1

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

2

Using iterative methods with queues can improve performance and avoid recursion limits in deep trees.

3

Early stopping on mismatch drastically reduces runtime in large unbalanced trees.

When NOT to use

Avoid symmetry checks when you need to verify exact tree equality or subtree containment; use tree equality or subtree algorithms instead.

Production Patterns

Used in graphical UI frameworks to verify mirrored layouts, in network topology checks for symmetric routing, and in compiler design for syntax tree transformations.

Connections

Tree Isomorphism

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

Understanding symmetry helps grasp the broader problem of tree isomorphism, which checks structural equivalence under any rearrangement.

Palindrome Checking

Both symmetry in trees and palindrome checking involve mirrored comparisons from opposite ends.

Recognizing this pattern helps transfer problem-solving skills between linear and hierarchical data structures.

Human Visual Symmetry Perception

The algorithm mimics how humans perceive symmetry by comparing mirrored halves.

Knowing this connection explains why symmetry checks feel intuitive and why they are important in design and aesthetics.

Common Pitfalls

#1 Confusing symmetry with identical trees and checking nodes in the same order.

Wrong approach:

def is_symmetric(t1, t2):
if not t1 and not t2:
return True
if not t1 or not t2:
return False
return (t1.val == t2.val and
is_symmetric(t1.left, t2.left) and
is_symmetric(t1.right, t2.right))

Correct approach:

def is_symmetric(t1, t2):
if not t1 and not t2:
return True
if not t1 or not t2:
return False
return (t1.val == t2.val and
is_symmetric(t1.left, t2.right) and
is_symmetric(t1.right, t2.left))

Root cause:

Misunderstanding that symmetry requires mirrored child comparisons, not identical child positions.

#2 Not handling null nodes properly, causing errors or wrong results.

Wrong approach:

def is_symmetric(t1, t2):
if t1.val != t2.val:
return False
return (is_symmetric(t1.left, t2.right) and is_symmetric(t1.right, t2.left))

Correct approach:

def is_symmetric(t1, t2):
if not t1 and not t2:
return True
if not t1 or not t2:
return False
if t1.val != t2.val:
return False
return (is_symmetric(t1.left, t2.right) and is_symmetric(t1.right, t2.left))

Root cause:

Forgetting to check if nodes are null before accessing their values.

Key Takeaways

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

Checking symmetry requires comparing the left subtree of one tree with the right subtree of the other recursively or iteratively.

Empty trees are symmetric by definition, and handling null nodes carefully prevents errors.

Recursive solutions are natural and simple, but iterative methods can handle large trees better.

Understanding symmetry helps in broader tree problems and real-world applications like UI design and network topology.

Practice

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

easy

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

B. They have the same number of nodes.

C. They have the same root value only.

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 A

4. Quick Check:

   Symmetry means mirror image = A [OK]

Hint: Symmetric trees mirror each other exactly [OK]

Common Mistakes:

• Thinking same number of nodes means symmetric
• Ignoring node values in comparison
• Checking only left or right subtree

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

easy

A. def is_symmetric(tree1, tree2)

B. def is_symmetric(tree1 tree2):

C. def is_symmetric(tree1, tree2) -> bool:

D. def is_symmetric(tree1, tree2): return True

Solution

1. Step 1: Check syntax for function definition

   Python functions require parentheses around parameters and a colon at the end.

2. Step 2: Identify correct type hint usage

   def is_symmetric(tree1, tree2) -> bool: uses correct syntax with type hint and colon, making it valid and clear.

3. Final Answer:

   def is_symmetric(tree1, tree2) -> bool: -> Option C

4. Quick Check:

   Correct Python function syntax with type hint = D [OK]

Hint: Use parentheses and colon; type hints are optional but clear [OK]

Common Mistakes:

• Missing comma between parameters
• Omitting colon at function end
• Incorrect parameter syntax without parentheses

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

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def is_mirror(t1, t2):
    if not t1 and not t2:
        return True
    if not t1 or not t2:
        return False
    return (t1.val == t2.val) and is_mirror(t1.left, t2.right) and is_mirror(t1.right, t2.left)

root1 = Node(1)
root1.left = Node(2)
root1.right = Node(3)

root2 = Node(1)
root2.left = Node(3)
root2.right = Node(2)

print(is_mirror(root1, root2))

medium

A. True

B. False

C. None

D. Error

Solution

1. Step 1: Check base cases for empty nodes

   Both trees have root 1, and their left and right children are swapped but equal in value.

2. Step 2: Recursively verify mirror condition

   Left of root1 (2) matches right of root2 (2), and right of root1 (3) matches left of root2 (3), so all conditions return True.

3. Final Answer:

   True -> Option A

4. Quick Check:

   Mirror check returns True for swapped children = A [OK]

Hint: Mirror means left of one equals right of other [OK]

Common Mistakes:

• Confusing left and right children in recursion
• Ignoring base cases for None nodes
• Assuming same structure means symmetric

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

def is_symmetric(t1, t2):
    if t1 is None and t2 is None:
        return True
    if t1 is None or t2 is None:
        return False
    if t1.val != t2.val:
        return False
    return is_symmetric(t1.left, t2.left) and is_symmetric(t1.right, t2.right)

medium

A. It does not check for None nodes.

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

C. It returns True too early without checking values.

D. It uses 'is' instead of '==' for value comparison.

Solution

1. Step 1: Analyze recursive calls for symmetry

   The function compares left subtree of t1 with left subtree of t2 and right with right, which is incorrect for mirror symmetry.

2. Step 2: Correct mirror comparison

   It should compare left of t1 with right of t2 and right of t1 with left of t2 to check mirror symmetry properly.

3. Final Answer:

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

4. Quick Check:

   Mirror check requires cross comparison = B [OK]

Hint: Mirror means cross compare left with right [OK]

Common Mistakes:

• Comparing same sides instead of mirror sides
• Confusing 'is' and '==' for values
• Missing base cases for None nodes

5. Given two binary trees, write a function to check if they are symmetric considering that one tree might be None. Which approach correctly handles this edge case?

hard

A. Return False immediately if either tree is None.

B. Ignore None checks and compare node values only.

C. Only compare root values and ignore subtrees.

D. Return True if both trees are None, else check mirror recursively.

Solution

1. Step 1: Handle None edge cases carefully

   If both trees are None, they are symmetric by definition, so return True.

2. Step 2: Recursively check mirror symmetry

   If only one is None, return False. Otherwise, compare root values and recursively check left of one with right of other and vice versa.

3. Final Answer:

   Return True if both trees are None, else check mirror recursively. -> Option D

4. Quick Check:

   Both None means symmetric, else recurse mirror check = C [OK]

Hint: Both None means symmetric; one None means not symmetric [OK]

Common Mistakes:

• Returning False if either tree is None without checking both
• Skipping recursive mirror checks
• Comparing only root values