Hello friends!

And, welcome to another tutorial on GeeksforGeeks. In this video we are going to understand the

program which helps us in converting a binary tree into its mirror tree.First let

us understand what exactly mirror of a binary tree means. Mirror of a Tree: Mirror of a Binary Tree

T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged.

Now, let us see the algorithm which will assist us in converting a binary tree into its

mirror tree. Let us also have a sample tree to test our

algorithm. First we pass the root node which is one into

function maxDepth. So node will point to 1. Since node is not null, we enter the else

part. Now we will calculate the depth or the height of the left and the right subtree

and return the maximum of the two +1. We call the maxDepth function recursively

to achieve this. We have Ldepth variable to store the depth of

the left subtree and rDepth variable to store the

depth of the right subtree. First, we have ldepth with the left child of 1 which is 2

passed as parameter. Since 2 is not null, we move on to the else

part, Now lDepth will be equal to maxDepth(4) which is the left child of 2. Now, the left child of 4 which is null is

passed to the maxDepth function. Since node is NULL, zero is returned Now we move on to the rDepth. The right child

of 4 which is NULL is passed into the call stack Since Node is Null, so 0 is returned Now, we compare the larger of the two and

return the larger+1. SInce both are equal we return 0+1 which is equal to 1 So, lDepth of 2 is one. Now we move to the

right depth of 2. Now we pass the right child of two which is 5. So node will

now point to 5. Since node is not null, we enter the else

part. Now the left child of 5 is passed which is NULL. Since node is NULL we return zero. Now we pass the right child of 5 which is

also NULL so we return 0 to rDepth for 5 Now we return the max of rDepth and lDepth

+1. Since both are 0 we return 0+1=1 to rDepth for node 2. Now we compare the lDepth and rDepth for node

2 and return the greater of them +1. Since both are equal we return 1+1 which

is equal to two. Next we move on to the right subtree of node

1.The right child of 1 which is 3 will be passed. So, node will now point to 3. Since 3 is not null, we enter the else part.

Now the left child of 3 is NULL so lDepth will be equal to maxDepth(NULL) Since node is null 0 is returned. So lDepth

for 3 will be equal to 0. Now the right child of three which is also

NULL is passed. So 0 is returned. NOw, the max of lDpepth and rightDepth +1

will be returned. So, 0+1 which is equal to 1 is returned. Now, we find the max of lDepth and rDepth

for node 1. Since lDepth is greater than rdepth we return lDepth+1 which is equal

to 3. THe final value returned is the height of

the tree. Now let us have a look at the time complexity of the program. This code will run in O(n) complexity.Heren

are the number of nodes in our tree. With this we come to an end of this tutorial. For any doubts or suggestions please leave

them in the comment section below. Thanks for watching!

## Ayush Agarwal

August 9, 2017thank you geeksforgeeks cheers!!

## chetan puttappanavar

August 10, 2017can you please tell me which is the good book for data structure

## Muthukumar Lakshmipathi

March 22, 2018we can add a condition to avoid unnecessary recursion for leafs

if(node->left != NULL && node->right != NULL) {

mirror(node->left);

mirror(node->right);

/* swap the pointers in this node */

temp = node->left;

node->left = node->right;

node->right = temp;

}