# Convert a Binary Tree to Its Mirror Tree

Posted in /   /  Ramya Shankar
Last updated on June 10, 2022

A binary tree is an important data structure. It has numerous applications in programming. A binary tree is a type of the tree data structure in which each node has two child nodes. In this tutorial, we will learn how to convert a binary tree to its mirror tree in C++, Java, and Python.

## Problem Statement

Given a binary tree, you need to convert it into its mirror tree. This problem is also known as inverting a binary tree problem.

#### Example ## Approach

We can use DFS to solve this problem. Consider a case when you need to convert the following binary tree into its mirror tree:

```      1
/     \
2       3```

We would simply swap the left and right children of the root. This algorithm can be extended on subtrees as well. We traverse a tree in any order and keep swapping left and right children for each node. Ultimately, this would result in the mirror image of the given tree. Most tree problems are solved by extending the algorithm as we did here.

### Complexity Analysis

The time complexity would be O(N), and the space complexity would also be O(N) in the worst case.

## How to Convert a Binary Tree to Its Mirror Tree?

Here, we will invert a binary tree in three different programming languages, namely C++, Java, and Python.

### 1. C++ Programming

```#include <iostream>
using namespace std;

struct TreeNode
{
int val;
TreeNode *left, *right;

TreeNode(int val)
{
this->val = val;
this->left = this->right = nullptr;
}
};

void printTree(TreeNode* root)
{
if (root == nullptr) {
return;
}

cout << root->val << " ";
printTree(root->left);
printTree(root->right);
}

bool dfs(TreeNode* root)
{
if (!root) {
return true;
}

// convert left subtree
dfs(root->left);

// convert right subtree
dfs(root->right);

// swap left subtree with right subtree
swap(root->left, root->right);
}

int main()
{
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);

dfs(root);

printTree(root);

return 0;
}```

#### Output

```1 3 2
```

### 2. Java Programming

```class TreeNode
{
int val;
TreeNode left = null, right = null;

TreeNode(int val) {
this.val = val;
}
}

class Main
{
public static void printTree(TreeNode root)
{
if (root == null) {
return;
}
System.out.print(root.val + " ");
printTree(root.left);
printTree(root.right);
}

public static void swap(TreeNode root)
{
if (root == null) {
return;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
}

public static void dfs(TreeNode root)
{
if (root == null) {
return;
}

// convert left subtree
dfs(root.left);

// convert right subtree
dfs(root.right);

// swap left subtree with right subtree
swap(root);
}

public static void main(String[] args)
{
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);

dfs(root);

printTree(root);
}
}```

#### Output

`1 3 2`

### 3. Python Programming

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

def printTree(root):
if root is None:
return

print(root.val, end=' ')
printTree(root.left)
printTree(root.right)

def swap(root):
if root is None:
return

temp = root.left
root.left = root.right
root.right = temp

def dfs(root):
if root is None:
return

# convert left subtree
dfs(root.left)

# convert right subtree
dfs(root.right)

# swap left subtree with right subtree
swap(root)

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
dfs(root)
printTree(root)```

1 3 2

## Conclusion

That sums up this tutorial on inverting a binary tree. We used the depth-first search for implementing the logic of converting a binary tree to its mirror tree. People are also reading: