Find Mirror of a Binary Tree - Algorithm, Visualization, Examples

Problem Statement❯

Given a binary tree, your task is to convert it into its mirror image. In a mirrored binary tree, the left and right children of all nodes are swapped recursively. You need to find this mirrored structure and optionally visualize or represent it in your preferred format.

Examples❯

Input Tree	Level Order Output	Description
[1, 2, 3, 4, 5, null, 6]	[[1], [3, 2], [6, 5, 4]]	Standard case: Mirror of a tree with three levels and uneven children
[1]	[[1]]	Edge case: Single-node tree remains the same when mirrored
[]	[]	Edge case: Empty tree has no mirror
[1, 2, null, 3, null, null, null, 4]	[[1], [null, 2], [null, 3], [null, 4]]	Left-skewed tree mirrored into a right-skewed structure
[1, null, 2, null, null, null, 3]	[[1], [2, null], [3, null]]	Right-skewed tree mirrored into a left-skewed structure
[7, 3, 9, 1, 5, 8, 10]	[[7], [9, 3], [10, 8, 5, 1]]	Full binary tree with mirrored structure at each level

Visualization Player

Solution❯

Case 1: Normal Binary Tree with Both Subtrees

In a typical binary tree where each node has both left and right children, mirroring is performed by swapping each node’s left and right child recursively. Starting at the root, you first swap the root's children, then apply the same operation on the new left and right subtrees. For example, a tree like [1, 2, 3] becomes [1, 3, 2]. This approach ensures the entire structure is flipped across a central vertical axis.

Case 2: Left-Skewed Tree

In a left-skewed tree (a tree where each node only has a left child), the mirror image will become a right-skewed tree. For example, the input [1, 2, null, 3] becomes [1, null, 2, null, 3]. Each node that originally had only a left child will now only have a right child. This transformation visually inverts the direction of the tree.

Case 3: Right-Skewed Tree

For a right-skewed tree (each node only has a right child), the mirror would be a left-skewed tree. For instance, [1, null, 2, null, 3] becomes [1, 2, null, 3]. The mirror process effectively flips the tree from right to left, following the same recursive swapping logic.

Case 4: Single-Node Tree

If the tree contains only one node, such as [1], the mirror of the tree will be the same as the original. There's no left or right child to swap, so the output remains unchanged. This is a natural base case for recursion when processing the mirror.

Case 5: Empty Tree

When the input tree is empty (represented as an empty array), the output is also an empty tree. There are no nodes to process, so this is the trivial base case where the function returns immediately or does nothing depending on implementation.

Algorithm Steps❯

Start at the root node of the binary tree.
If the current node is null, return.
Swap the left and right children of the current node.
Recursively call the mirror function on the left subtree.
Recursively call the mirror function on the right subtree.
The binary tree is now mirrored.

Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

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

def mirror(root):
    if root is None:
        return
    root.left, root.right = root.right, root.left
    mirror(root.left)
    mirror(root.right)
    return root

# Example usage:
if __name__ == '__main__':
    # Construct binary tree:
    #         1
    #        / \
    #       2   3
    #      /   / \
    #     4   5   6
    root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3, TreeNode(5), TreeNode(6)))
    mirror(root)
    # The tree is now transformed into its mirror image

⬅ Previous TopicFind Diameter of a Binary Tree

Next Topic ⮕Left View of a Binary Tree

Comments

Loading comments...