Check if Two Binary Trees are Mirror Images - Algorithm, Visualization, Examples

Contents

ProblemExamplesSolutionAlgorithmCode

Problem Statement❯

Given two binary trees, your task is to determine whether they are mirror images of each other. Two trees are said to be mirrors if the structure of one tree is the reverse of the other and their corresponding node values are the same. This check must be done recursively for all corresponding nodes.

Examples❯

Tree 1 Tree 2 Are Mirror? Description
[1, 2, 3, 4, 5]
[1, 3, 2, null, null, 5, 4]
true Tree 2 is the mirror image of Tree 1: left and right children are swapped at every node.
[10, 20, 30]
[10, 30, 20]
true Left and right subtrees are perfectly mirrored.
[1, 2, 3]
[1, 2, 3]
false Both trees have the same structure, but are not mirrors (no left-right reversal).
[] [] true Two empty trees are trivially mirrors of each other.
[1]
[1]
true Single-node trees with the same value are mirrors.
[1, 2]
[1, null, 2]
true Tree 1 has a left child; Tree 2 has a right child. Structures mirror each other.

Solution❯

Case 1: Both Trees Are Empty

If both trees are completely empty (null), they are considered mirror images by definition. This is the simplest and most direct case. There's nothing to compare, and yet they reflect each other perfectly in absence.

Case 2: One Tree is Empty, the Other is Not

In this case, the trees cannot be mirrors. A mirror image implies that both trees must at least have the same number of levels and nodes (albeit in mirrored structure). If one is null and the other is not, the symmetry breaks immediately.

Case 3: Root Nodes Have Different Values

If the values at the root nodes of the two trees are different, they cannot be mirrors. The concept of a mirror requires that not only the structure but the data in corresponding mirrored positions must match.

Case 4: Root Values Match — Compare Subtrees

If the root values are the same, we recursively compare the left subtree of the first tree with the right subtree of the second tree, and the right subtree of the first with the left subtree of the second. Both comparisons must succeed for the trees to be considered mirrors.

Case 5: Trees Have Partial Mirror Structure

Sometimes, the trees may start as mirrors but differ deeper down in structure or values. For instance, if the root and immediate children match in a mirrored way but the grandchildren do not reflect each other, then the trees are not mirrors. Every level of the tree must satisfy the mirror property.

Case 6: Single Node Trees

Two single-node trees with the same value are mirrors of each other, since there's no child to compare. But if one has children and the other doesn't, they are not mirrors. Even having a child on different sides breaks the mirror property.

Algorithm Steps❯

  1. Given two binary trees, if both trees are empty, they are mirrors; if one is empty and the other is not, they are not mirrors.
  2. Compare the root nodes of both trees. If the values are not equal, the trees are not mirrors.
  3. Recursively check if the left subtree of the first tree is a mirror of the right subtree of the second tree, and if the right subtree of the first tree is a mirror of the left subtree of the second tree.
  4. If both recursive checks return true, then the two trees are mirror images of each other.

Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

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

# Example usage:
if __name__ == '__main__':
    # Tree 1:
    #      1
    #     / \
    #    2   3
    #
    # Tree 2 (mirror of Tree 1):
    #      1
    #     / \
    #    3   2
    tree1 = TreeNode(1, TreeNode(2), TreeNode(3))
    tree2 = TreeNode(1, TreeNode(3), TreeNode(2))
    print(isMirror(tree1, tree2))