# Convert a Binary Tree to Its Mirror Tree

By | October 25, 2021

## Problem

Given a binary tree, you need to convert it into its mirror image. 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 the 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 of the 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.

#### 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;
}```

```1 3 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);
}
}```

`1 3 2`

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