Given two binary trees, write a function to Check Two Binary Trees are Mirror Images or Symmetric, or not. For two trees to be mirror images, the following conditions must be true
-
The root node must be the same for both Trees.
-
The left subtree of the first Tree must be the mirror of the right subtree of the Second Tree.
-
The right subtree of the first Tree must be the mirror of the left subtree of the Second Tree.
Code Flow for Check Two Binary Trees are Mirror Images or Symmetric
-
Base Case:
- If both
rootAandrootBarenull(empty trees), They are mirrors by definition, so the method returnstrue.
- If both
-
Another Base Case:
- If one of the trees is
nulland the other is not, they cannot be mirrors, so the method returnsfalse.
- If one of the trees is
-
Recursive Case:
-
The method checks three conditions:
-
The root values of both trees (
rootA.dataandrootB.data) should be equal. -
The left subtree of
rootAshould be a mirror of the right subtree ofrootB, and vice versa. -
The method recursively calls
checkMirrorfor both left and right subtrees, flipping them (left of one tree compared with right of the other, and vice versa).
-
-
Let's see the code now
package org.wesome.dsalgo;
import lombok.Data;
import java.util.Objects;
public class BinaryTree {
Node root;
public boolean checkMirror(Node rootA, Node rootB) {
/* If both rootA and rootB are null (empty trees), they are mirrors by definition, so the method returns true. */
if (Objects.isNull(rootA) && Objects.isNull(rootB)) {
return true;
}
/* If one of the trees is null and the other is not, they cannot be mirrors, so the method returns false. */
if (Objects.isNull(rootA) || Objects.isNull(rootB)) {
return false;
}
/* The root values of both trees (rootA.data and rootB.data) should be equal. */
return (rootA.data == rootB.data)
/* The left subtree of rootA should be a mirror of the right subtree of rootB */
&& checkMirror(rootA.left, rootB.right)
/* The right subtree of rootA should be a mirror of the left subtree of rootB */
&& checkMirror(rootA.right, rootB.left);
}
}
@Data
class Node {
int data;
Node left, right;
public Node(int data) {
this.data = data;
left = right = null;
}
}
package org.wesome.dsalgo;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertTrue;
public class BinaryTreeTest {
@Test
void testNullTree() {
BinaryTree binaryTree = new BinaryTree();
assertTrue(binaryTree.checkMirror(null, null), "Both trees are null, should return true");
}
@Test
public void testOneTreeIsNull() {
// Constructing the following tree:
// 1
// / \
// 2 3
// / \
// 4 5
BinaryTree binaryTree = new BinaryTree();
Node nodeA = new Node(1);
nodeA.left = new Node(2);
nodeA.right = new Node(3);
nodeA.left.left = new Node(4);
nodeA.left.right = new Node(5);
assertFalse(binaryTree.checkMirror(null, nodeA), "One tree is null and the other is not, should return false");
assertFalse(binaryTree.checkMirror(nodeA, null), "One tree is null and the other is not, should return false");
}
@Test
void testSingleNodeTree() {
BinaryTree binaryTree = new BinaryTree();
Node rootA = new Node(0);
Node rootB = new Node(0);
assertTrue(binaryTree.checkMirror(rootA, rootB));
}
@Test
void testMirrorTree() {
BinaryTree binaryTree = new BinaryTree();
Node rootA = new Node(10);
rootA.left = new Node(5);
rootA.right = new Node(15);
rootA.left.left = new Node(2);
rootA.left.right = new Node(7);
rootA.right.left = new Node(12);
rootA.right.right = new Node(18);
Node rootB = new Node(10);
rootB.right = new Node(5);
rootB.left = new Node(15);
rootB.right.right = new Node(2);
rootB.right.left = new Node(7);
rootB.left.right = new Node(12);
rootB.left.left = new Node(18);
assertTrue(binaryTree.checkMirror(rootA, rootB));
}
@Test
void testTreeWithDuplicateValues() {
// Constructing the following tree:
// 1
// / \
// 1 1
// / \ / \
// 1 1 1 1
BinaryTree binaryTree = new BinaryTree();
Node rootA = new Node(1);
rootA.left = new Node(1);
rootA.right = new Node(1);
rootA.left.left = new Node(1);
rootA.left.right = new Node(1);
rootA.right.left = new Node(1);
rootA.right.right = new Node(1);
Node rootB = new Node(1);
rootB.left = new Node(1);
rootB.right = new Node(1);
rootB.left.left = new Node(1);
rootB.left.right = new Node(1);
rootB.right.left = new Node(1);
rootB.right.right = new Node(1);
assertTrue(binaryTree.checkMirror(rootA, rootB));
}
@Test
public void testTreesWithSameStructureButDifferentValues() {
// Constructing the following tree:
// 1
// / \
// 2 3
// / \
// 4 5
BinaryTree binaryTree = new BinaryTree();
Node rootA = new Node(1);
rootA.left = new Node(2);
rootA.right = new Node(3);
rootA.left.left = new Node(4);
rootA.left.right = new Node(5);
// Constructing the following tree:
// 10
// / \
// 20 30
// / \
// 40 50
Node rootB = new Node(10);
rootB.left = new Node(20);
rootB.right = new Node(30);
rootB.left.left = new Node(40);
rootB.left.right = new Node(50);
assertFalse(binaryTree.checkMirror(rootA, rootB), "Trees have different values, should return false");
}
@Test
public void testTreesWithAdditionalNode() {
// Constructing the following tree:
// 1
// / \
// 2 3
// / \
// 4 5
BinaryTree binaryTree = new BinaryTree();
Node rootA = new Node(1);
rootA.left = new Node(2);
rootA.right = new Node(3);
rootA.left.left = new Node(4);
rootA.left.right = new Node(5);
// Constructing the following tree:
// 10
// / \
// 20 30
// / \
// 40 50
// \
// 60
Node rootB = new Node(10);
rootB.left = new Node(20);
rootB.right = new Node(30);
rootB.left.left = new Node(40);
rootB.left.right = new Node(50);
rootB.left.right.right = new Node(60);
assertFalse(binaryTree.checkMirror(rootA, rootB), "Trees have different values, should return false");
}
@Test
void testSameTree() {
// Constructing the following tree:
// 1
// / \
// 2 3
// / \
// 4 5
BinaryTree binaryTree = new BinaryTree();
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
assertFalse(binaryTree.checkMirror(root, root));
}
@Test
void testTreeWithSameValues() {
// Constructing the following tree:
// 1
// / \
// 1 1
// / \ / \
// 1 1 1 1
BinaryTree binaryTree = new BinaryTree();
Node root = new Node(1);
root.left = new Node(1);
root.right = new Node(1);
root.left.left = new Node(1);
root.left.right = new Node(1);
root.right.left = new Node(1);
root.right.right = new Node(1);
assertTrue(binaryTree.checkMirror(root, root));
}
}
plugins {
id("java")
id("io.freefair.lombok") version "8.13"
}
group = "org.wesome.dsalgo"
version = "1.0-SNAPSHOT"
repositories {
mavenCentral()
}
dependencies {
testImplementation(platform("org.junit:junit-bom:5.10.0"))
testImplementation("org.junit.jupiter:junit-jupiter")
}
tasks.test {
useJUnitPlatform()
}Complexity Analysis
Time Complexity
O(n) where n is the total number of nodes in the trees.
Space Complexity
O(h) where h is the height of the tree (can be as bad as O(n) for a skewed tree or O(log n) for a balanced tree).
