ProgramGuru

Find Mirror of a Binary Tree

Problem and examples

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.
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

Explore Find Mirror of a Binary Tree

Load an example or enter your own input. Use the player controls to follow each change.

Understanding the Problem

We are given a binary tree and asked to return its mirror image. Mirroring a binary tree means swapping the left and right subtrees of every node in the tree recursively. The root stays the same, but its children, and all children below, are flipped horizontally. This transformation turns a left-heavy tree into a right-heavy one and vice versa.

The challenge lies in performing this transformation correctly for all types of binary trees — including balanced trees, skewed trees, and edge cases like a single-node or empty tree.

Step-by-Step Solution with Example

Step 1: Define the Task Clearly

We want to traverse the binary tree and, for every node we visit, swap its left and right child. This needs to be done for all nodes in the tree, which means recursion is a natural fit.

Step 2: Pick an Example

Let’s take a simple binary tree:


        1
       /       2   3

Its mirror image would look like this:


        1
       /       3   2

Step 3: Recursively Swap Children

Starting at the root node (1), we swap the left (2) and right (3) children. Then, we go deeper and apply the same swapping logic recursively on node 2 and node 3.

If node 2 and 3 have children, their left and right children would also be swapped, and so on.

Step 4: Write the Recursive Logic

The recursive steps can be described as:

  1. If the current node is null, return null (base case)
  2. Swap its left and right child
  3. Recursively call the function on the left child
  4. Recursively call the function on the right child

Edge Cases

Case 1: Left-Skewed Tree

Example: [1, 2, null, 3] becomes [1, null, 2, null, 3]

This demonstrates how the left-only structure becomes right-only after mirroring.

Case 2: Right-Skewed Tree

Example: [1, null, 2, null, 3] becomes [1, 2, null, 3]

Right-only nodes become left-only, following the same recursive logic.

Case 3: Single Node Tree

Input: [1]
Output remains: [1]

Since there's no child to swap, the tree stays the same.

Case 4: Empty Tree

Input: [] → Output: []

No nodes to process. Function should handle this safely and return null or equivalent.

Finally

This problem is a classic example of recursive tree traversal. By understanding the structure of the binary tree and applying a simple left-right swap at every node, we can generate its mirror efficiently.

It’s important to consider edge cases like null nodes, skewed trees, and minimal structures during implementation. Always test your function with various types of trees to ensure robustness.

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

Implementation and efficiency

C implementation

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

TreeNode* mirror(TreeNode* root) {
    if (root == NULL) return NULL;
    TreeNode* temp = root->left;
    root->left = root->right;
    root->right = temp;
    mirror(root->left);
    mirror(root->right);
    return root;
}

int main() {
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->right->left = createNode(5);
    root->right->right = createNode(6);
    mirror(root);
    printf("Tree mirrored successfully\n");
    return 0;
}

C++ implementation

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* mirror(TreeNode* root) {
    if (!root) return nullptr;
    TreeNode* temp = root->left;
    root->left = root->right;
    root->right = temp;
    mirror(root->left);
    mirror(root->right);
    return root;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->right->left = new TreeNode(5);
    root->right->right = new TreeNode(6);
    mirror(root);
    cout << "Tree mirrored successfully" << endl;
    return 0;
}

Python implementation

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

if __name__ == '__main__':
    root = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3, TreeNode(5), TreeNode(6)))
    mirror(root)
    print("Tree mirrored successfully")

Java implementation

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class MirrorBinaryTree {
    public static TreeNode mirror(TreeNode root) {
        if (root == null) return null;
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        mirror(root.left);
        mirror(root.right);
        return root;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(6);
        mirror(root);
        System.out.println("Tree mirrored successfully");
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function mirror(root) {
    if (!root) return null;
    [root.left, root.right] = [root.right, root.left];
    mirror(root.left);
    mirror(root.right);
    return root;
}

const root = new TreeNode(1, 
    new TreeNode(2, new TreeNode(4)), 
    new TreeNode(3, new TreeNode(5), new TreeNode(6))
);
mirror(root);
console.log("Tree mirrored successfully");

Go implementation

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func mirror(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    root.Left, root.Right = root.Right, root.Left
    mirror(root.Left)
    mirror(root.Right)
    return root
}

func main() {
    root := &TreeNode{1,
        &TreeNode{2, &TreeNode{4, nil, nil}, nil},
        &TreeNode{3, &TreeNode{5, nil, nil}, &TreeNode{6, nil, nil}},
    }
    mirror(root)
    fmt.Println("Tree mirrored successfully")
}

Rust implementation

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

fn mirror(node: &mut Option<Box<TreeNode>>) {
    if let Some(ref mut root) = node {
        std::mem::swap(&mut root.left, &mut root.right);
        mirror(&mut root.left);
        mirror(&mut root.right);
    }
}

fn main() {
    let mut root = Some(Box::new(TreeNode {
        val: 1,
        left: Some(Box::new(TreeNode {
            val: 2,
            left: Some(Box::new(TreeNode { val: 4, left: None, right: None })),
            right: None,
        })),
        right: Some(Box::new(TreeNode {
            val: 3,
            left: Some(Box::new(TreeNode { val: 5, left: None, right: None })),
            right: Some(Box::new(TreeNode { val: 6, left: None, right: None })),
        })),
    }));
    mirror(&mut root);
    println!("Tree mirrored successfully");
}

Kotlin implementation

class TreeNode(var value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun mirror(root: TreeNode?): TreeNode? {
    if (root == null) return null
    val temp = root.left
    root.left = root.right
    root.right = temp
    mirror(root.left)
    mirror(root.right)
    return root
}

fun main() {
    val root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left?.left = TreeNode(4)
    root.right?.left = TreeNode(5)
    root.right?.right = TreeNode(6)
    mirror(root)
    println("Tree mirrored successfully")
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?

    init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

func mirror(_ root: TreeNode?) -> TreeNode? {
    guard let root = root else { return nil }
    (root.left, root.right) = (root.right, root.left)
    _ = mirror(root.left)
    _ = mirror(root.right)
    return root
}

let root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left?.left = TreeNode(4)
root.right?.left = TreeNode(5)
root.right?.right = TreeNode(6)
_ = mirror(root)
print("Tree mirrored successfully")

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function mirror(root: TreeNode | null): TreeNode | null {
    if (!root) return null;
    [root.left, root.right] = [root.right, root.left];
    mirror(root.left);
    mirror(root.right);
    return root;
}

const root = new TreeNode(1,
    new TreeNode(2, new TreeNode(4)),
    new TreeNode(3, new TreeNode(5), new TreeNode(6))
);
mirror(root);
console.log("Tree mirrored successfully");