Create Mirror Image or Symmetric Binary Tree

Given a binary tree. Write a function to Create Mirror Image or Symmetric Binary Tree. A mirror of a binary tree is created by recursively swapping the left and right children at each level, starting from the root and working down to the leaf nodes.
The entire tree is traversed in a post-order fashion (left subtree, right subtree, then node itself), swapping the left and right children at each step and ultimately creating a mirror image of the binary tree.

Code Flow for Create Mirror Image or Symmetric Binary Tree

• Base Case Check:

  • The first line checks if the node is null using Objects.isNull(node).

  • If the node is null, the method returns null. This is the base case for the recursion, which handles leaf nodes and empty subtrees.

• Recursive Calls:

  • The method makes recursive calls to mirror the left and right subtrees of the current node:

    • left = mirror(node.left): Recursively mirrors the left child of the current node.

    • right = mirror(node.right): Recursively mirrors the right child of the current node.

• Swap Left and Right Subtrees:

  • After the recursive calls, the method swaps the left and right children of the current node:

    • node.left = right: Assigns the mirrored right child to the left child of the current node.

    • node.right = left: Assigns the mirrored left child to the right child of the current node.

• Return the Node:

  • Finally, the method returns the current node (node) with its children swapped (this is the mirrored node).

Let's see the code now

package org.wesome.dsalgo;

import lombok.Data;

import java.util.Objects;

public class BinaryTree {
    Node root;

    public Node mirror(Node node) {
        /*  If the node is null, the method returns null. This is the base case for the recursion, which handles leaf nodes and empty subtrees. */
        if (Objects.isNull(node)) {
            return null;
        }

        /*  make recursive calls to mirror the left and right subtrees of the current node  */
        Node left = mirror(node.left);
        Node right = mirror(node.right);

        /* swap the left and right subtree */
        /*   Assigns the mirrored right child to the left child of the current node.    */
        node.left = right;
        /*  Assigns the mirrored left child to the right child of the current node. */
        node.right = left;
        return node;
    }

    /* Inorder -> Left -> Root -> Right */
  void printInOrder(Node root) {
        if (Objects.isNull(root)) {
            return;
        }
        printInOrder(root.left);
        System.out.print(" " + root.data);
        printInOrder(root.right);
    }

    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;

public class BinaryTreeTest {

    @Test
    void testEmptyTree() {
        // Test for an empty tree (null root)
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.printInOrder(binaryTree.root);
        Node mirror = binaryTree.mirror(null);
        binaryTree.printInOrder(mirror);
    }

    @Test
    void testSingleNodeTree() {
        // Test for a tree with a single node
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.insert(10);
        binaryTree.printInOrder(binaryTree.root);
        Node mirror = binaryTree.mirror(binaryTree.root);
        binaryTree.printInOrder(mirror);
    }

    @Test
    void testBalancedBinaryTree() {
        // Test for a balanced binary tree
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.insert(10);
        binaryTree.insert(5);
        binaryTree.insert(15);
        binaryTree.insert(2);
        binaryTree.insert(7);
        binaryTree.insert(12);
        binaryTree.insert(18);
        binaryTree.printInOrder(binaryTree.root);
        Node mirror = binaryTree.mirror(binaryTree.root);
        binaryTree.printInOrder(mirror);
    }

    @Test
    void testUnbalancedBinaryTree() {
        // Test for an unbalanced binary tree (sorted order insertion creating a right-skewed tree)
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.insert(10);
        binaryTree.insert(20);
        binaryTree.insert(30);
        binaryTree.insert(40);
        binaryTree.insert(50);
        binaryTree.printInOrder(binaryTree.root);
        Node mirror = binaryTree.mirror(binaryTree.root);
        binaryTree.printInOrder(mirror);
    }

    @Test
    void testTreeWithNegativeValues() {
        // Test for a tree with negative values
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.insert(-5);
        binaryTree.insert(-3);
        binaryTree.insert(-2);
        binaryTree.insert(-1);
        binaryTree.insert(-7);
        binaryTree.insert(-4);
        binaryTree.printInOrder(binaryTree.root);
        Node mirror = binaryTree.mirror(binaryTree.root);
        binaryTree.printInOrder(mirror);
    }

    @Test
    void testLargeTree() {
        // Test for a large tree with many nodes
        BinaryTree binaryTree = new BinaryTree();
        for (int i = 1; i <= 1000; i++) {
            binaryTree.insert(i);
        }
        binaryTree.printInOrder(binaryTree.root);
        Node mirror = binaryTree.mirror(binaryTree.root);
        binaryTree.printInOrder(mirror);
    }

    @Test
    void testBalancedTree() {
        BinaryTree binaryTree = new BinaryTree();
        Node root = new Node(10);
        root.left = new Node(5);
        root.right = new Node(15);
        root.left.left = new Node(2);
        root.left.right = new Node(7);
        root.right.left = new Node(12);
        root.right.right = new Node(18);
        binaryTree.printInOrder(root);
        Node mirror = binaryTree.mirror(root);
        binaryTree.printInOrder(mirror);
    }

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

        BinaryTree binaryTree = new BinaryTree();
        Node root = new Node(10);
        root.right = new Node(20);
        root.right.right = new Node(30);
        root.right.right.right = new Node(40);
        root.right.right.right.right = new Node(50);
        binaryTree.printInOrder(root);
        Node mirror = binaryTree.mirror(root);
        binaryTree.printInOrder(mirror);
    }

    @Test
    void testTreeWithDuplicateValues() {
        // 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);
        binaryTree.printInOrder(root);
        Node mirror = binaryTree.mirror(root);
        binaryTree.printInOrder(mirror);
    }

    @Test
    void testTreeBinaryTreeValues() {
        // 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);
        binaryTree.printInOrder(root);
        binaryTree.printInOrder(root);
        Node mirror = binaryTree.mirror(root);
        binaryTree.printInOrder(mirror);
    }
}

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()
}