Check if Two Trees are Mirror Structures

Given a Binary Tree, the task is to check if Two Trees are Mirror structures to each other,

Two trees are considered mirrors of each other if:

The structure (or shape) of the trees is identical but mirrored. This means:
- The left subtree of the first tree should be a mirror of the right subtree of the second tree.
- The right subtree of the first tree should be a mirror of the left subtree of the second tree.
The values of the nodes are not necessary to be the same i.e., it is only the structure that matters, not the data in the nodes.

Code Flow for Check if Two Trees are Mirror Structures

The function checkMirrorStructure checks if the two binary trees rooted at node1 and node2 are mirror images of each other.
Base Case 1: If both node1 and node2 are null, it returns true because both trees are empty and thus mirror images.
Base Case 2: If one of the nodes is null and the other is not, it returns false because one tree is empty, and the other is not.
Recursive Step: It recursively checks:
- The left subtree of node1 against the right subtree of node2.
- The right subtree of node1 against the left subtree of node2.
Both conditions must be true for the trees to be mirrors of each other.

Let's see the code now

package org.wesome.dsalgo;

import lombok.Data;

import java.util.Objects;

public class BinarySearchTree {
    Node root;

    public static boolean checkMirrorStructure(Node node1, Node node2) {
        /*  If both node1 and node2 are null, it means both trees are empty or we’ve reached the end of both trees at the same level.   */
        if (Objects.isNull(node1) && Objects.isNull(node2)) {
            System.out.println("BinarySearchTree.checkMirrorStructure both nodes are null");
            return true;
        }
        /*  If only one of the nodes (node1 or node2) is null, it means the trees are not mirror images, because a tree cannot be a mirror of another if one of the trees is missing a node at any corresponding position.  */
        if (Objects.isNull(node1) || Objects.isNull(node2)) {
            System.out.println("BinarySearchTree.checkMirrorStructure 1 of the node is null");
            return false;
        }
        /*  checks if the left subtree of node1 is a mirror of the right subtree of node2, and if the right subtree of node1 is a mirror of the left subtree of node2.  */
        return checkMirrorStructure(node1.left, node2.right) && checkMirrorStructure(node1.right, node2.left);
    }

    void insert(int data) {
        System.out.println("BinarySearchTree.insert data = " + data);
        root = insert(root, data);
    }

    Node insert(Node root, int data) {
        if (Objects.isNull(root)) {
            Node tempNode = new Node(data);
            return tempNode;
        }
        if (data > root.data) {
            root.right = insert(root.right, data);
        } else {
            root.left = insert(root.left, data);
        }
        return root;
    }
}

@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;
import static org.wesome.dsalgo.BinarySearchTree.checkMirrorStructure;

public class BinaryTreeTest {

    @Test
    public void testBothTreesAreNull() {
        assertTrue(checkMirrorStructure(null, null), "Both trees are null, should return true");
    }

    @Test
    public void testOneTreeIsNull() {
        Node tree1 = new Node(1);
        Node tree2 = null;
        assertFalse(checkMirrorStructure(tree1, tree2), "One tree is null, should return false");
    }

    @Test
    public void testBothTreesAreSingleNodes() {
        Node tree1 = new Node(1);
        Node tree2 = new Node(1);
        assertTrue(checkMirrorStructure(tree1, tree2), "Both trees are single nodes with the same value, should return true");
    }

    @Test
    public void testTreesWithDifferentRootValues() {
        Node tree1 = new Node(1);
        Node tree2 = new Node(1);
        assertTrue(checkMirrorStructure(tree1, tree2), "Trees with different root values, but same structure should return true");
    }

    @Test
    public void testTreesWithSingleSubtree() {
        Node tree1 = new Node(1);
        tree1.left = new Node(2);
        Node tree2 = new Node(1);
        tree2.right = new Node(2);
        assertTrue(checkMirrorStructure(tree1, tree2), "Both trees have one subtree, should return true");
    }

    @Test
    public void testTreesAreMirrorsOfEachOther() {
        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(checkMirrorStructure(rootA, rootB), "Both trees are mirrors of each other, should return true");
    }

    @Test
    public void testTreesWithDifferentStructures() {
        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(1);
        rootB.right = new Node(2);
        rootB.left = new Node(3);
        rootB.right.right = new Node(4);
        rootB.right.right.right = new Node(5);
        rootB.right.right.left = new Node(6);
        rootB.right.left = new Node(7);
        rootB.right.left.right = new Node(8);
        rootB.right.left.left = new Node(9);
        rootB.left.right = new Node(10);
        rootB.left.left = new Node(11);
        assertFalse(checkMirrorStructure(rootA, rootB), "Trees with different structures, should return false");
    }

    @Test
    public void testTreesWithAdditionalNode() {
        // Constructing the following tree:
        //       1
        //      / \
        //     2   3
        //    / \
        //   4   5

        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(checkMirrorStructure(rootA, rootB), "Trees with symmetric structure, should return true");
    }


    @Test
    void testTreeWithSameValues() {
        // Constructing the following tree:
        //          1
        //       /    \
        //      1       1
        //     / \     / \
        //    1   1   1   1

        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(checkMirrorStructure(root, root), "Same Trees, should return true");
    }


    @Test
    void testSkewedTree() {
        // Constructing the following tree:
        //          10
        //           \
        //            20
        //             \
        //              30
        //               \
        //                40
        //                 \
        //                  50

        //                  10
        //                 /
        //                20
        //               /
        //              30
        //             /
        //           40
        //          /
        //         50

        Node rootA = new Node(10);
        rootA.right = new Node(20);
        rootA.right.right = new Node(30);
        rootA.right.right.right = new Node(40);
        rootA.right.right.right.right = new Node(50);

        Node rootB = new Node(10);
        rootB.left = new Node(20);
        rootB.left.left = new Node(30);
        rootB.left.left.left = new Node(40);
        rootB.left.left.left.left = new Node(50);
        assertTrue(checkMirrorStructure(rootA, rootB), "Skewed Trees, should return true");
    }
}

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:

The time complexity is O(n), where n is the number of nodes in the trees. This is because we visit each node once during the recursion.

Space Complexity:

The space complexity is O(h), where h is the height of the tree. This is because of the recursive stack used for the function calls.

Check if Two Trees are Mirror Structures

Code Flow for Check if Two Trees are Mirror Structures

Complexity Analysis

Time Complexity:

Space Complexity:

follow us on