Register for our webinar

How to Nail your next Technical Interview

1 hour
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
Step 1
Step 2
Congratulations!
You have registered for our webinar
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.

You may be missing out on a 66.5% salary hike*

Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Help us know you better!

How many years of coding experience do you have?

Oops! Something went wrong while submitting the form.

FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Oops! Something went wrong while submitting the form.

Mirror Image Of Binary Tree Problem

Coding problems on trees are asked frequently at tech interviews. Creating a mirror tree from the given binary tree is one such popular DSA problem. Let's look at what the problem entails and how to solve it.

Mirror Image Of Binary Tree Problem Statement

Given the root of a binary tree, transform the tree in-place into its mirror image.

Example

``````        0
/   \
1       2
/  \   /   \
3    4  5    6
``````

Output:

``````         0
/    \
2        1
/  \    /   \
6    5   4    3
``````

Notes

• The function doesn't need to return anything. Modify the tree in-place.

Constraints:

• 1 <= number of nodes <= 100000
• 0 <= node value < number of nodes
• Node values are unique

We provided two solutions: a recursive one and an iterative one.

We will refer to the total number of nodes in the given tree as `n`.

Mirror Image Of Binary Tree Solution 1: Depth First Search

This is a recursive solution. The main task is to swap left and right children for every node of the tree. We are calling the function recursively and making sure that leaf nodes are handled first then their parents and it goes up to the root node.

O(n).

Auxiliary Space Used

O(n).

That extra space is used for the call stack.

Space Complexity

O(n).

Input is O(n) because we are storing `n` nodes relationships and each relationship occupies O(1) space and auxiliary space used is O(n). So, O(n) + O(n) = O(n).

Code For Mirror Image Of Binary Tree Solution 1: Depth First Search

``````    /*
* Asymptotic complexity in terms of number of nodes \`n\` in the given tree:
* Time: O(n).
* Auxiliary space: O(n).
* Total space: O(n).
*/

public static void mirror_image(BinaryTreeNode root) {
root = mirror_image_util(root);
}

public static BinaryTreeNode mirror_image_util(BinaryTreeNode root){
if (root == null)
return root;

BinaryTreeNode left = mirror_image_util(root.left);
BinaryTreeNode right = mirror_image_util(root.right);

// Swap the left and right pointers.
root.left = right;
root.right = left;
return root;
}
``````

Mirror Image Of Binary Tree Solution 2: Breadth First Search

This solution traverses the tree breadth first using a loop and a queue, without making use of recursion. We initialize the queue with the root node. Then we do the following until the queue is empty:

• Get next node from the queue
• Swap its left and right child nodes
• Push its left and right children into the queue

O(n).

Auxiliary Space Used

O(n).

We are using a queue for storing nodes to do BFS traversal over the tree. In the worst case scenario, queue size will be `n`.

Space Complexity

O(n).

Input is O(n) because we are storing `n` nodes relationships and each relationship occupies O(1) space and auxiliary space used is O(n). So, O(n) + O(n) = O(n).

Code For Mirror Image Of Binary Tree Solution 2: Breadth First Search

``````    /*
* Asymptotic complexity in terms of number of nodes \`n\` in the given tree:
* Time: O(n).
* Auxiliary space: O(n).
* Total space: O(n).
*/

public static void mirror_image(BinaryTreeNode root) {
if (root == null)
return;

// Do BFS. While doing BFS, keep swapping
// left and right children
while(!queue.isEmpty()) {
// Pop top node from queue.
BinaryTreeNode cur_node = queue.poll();

// Swap left child with right child.
BinaryTreeNode temp = cur_node.left;
cur_node.left = cur_node.right;
cur_node.right = temp;

// Push left and right children.
if (cur_node.left != null)
if (cur_node.right != null)
}
}
``````

We hope that these solutions to creating a mirror image of a binary tree have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 17 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

Try yourself in the Editor

Note: Input and Output will already be taken care of.

Mirror Image Of Binary Tree Problem

Coding problems on trees are asked frequently at tech interviews. Creating a mirror tree from the given binary tree is one such popular DSA problem. Let's look at what the problem entails and how to solve it.

Mirror Image Of Binary Tree Problem Statement

Given the root of a binary tree, transform the tree in-place into its mirror image.

Example

``````        0
/   \
1       2
/  \   /   \
3    4  5    6
``````

Output:

``````         0
/    \
2        1
/  \    /   \
6    5   4    3
``````

Notes

• The function doesn't need to return anything. Modify the tree in-place.

Constraints:

• 1 <= number of nodes <= 100000
• 0 <= node value < number of nodes
• Node values are unique

We provided two solutions: a recursive one and an iterative one.

We will refer to the total number of nodes in the given tree as `n`.

Mirror Image Of Binary Tree Solution 1: Depth First Search

This is a recursive solution. The main task is to swap left and right children for every node of the tree. We are calling the function recursively and making sure that leaf nodes are handled first then their parents and it goes up to the root node.

O(n).

Auxiliary Space Used

O(n).

That extra space is used for the call stack.

Space Complexity

O(n).

Input is O(n) because we are storing `n` nodes relationships and each relationship occupies O(1) space and auxiliary space used is O(n). So, O(n) + O(n) = O(n).

Code For Mirror Image Of Binary Tree Solution 1: Depth First Search

``````    /*
* Asymptotic complexity in terms of number of nodes \`n\` in the given tree:
* Time: O(n).
* Auxiliary space: O(n).
* Total space: O(n).
*/

public static void mirror_image(BinaryTreeNode root) {
root = mirror_image_util(root);
}

public static BinaryTreeNode mirror_image_util(BinaryTreeNode root){
if (root == null)
return root;

BinaryTreeNode left = mirror_image_util(root.left);
BinaryTreeNode right = mirror_image_util(root.right);

// Swap the left and right pointers.
root.left = right;
root.right = left;
return root;
}
``````

Mirror Image Of Binary Tree Solution 2: Breadth First Search

This solution traverses the tree breadth first using a loop and a queue, without making use of recursion. We initialize the queue with the root node. Then we do the following until the queue is empty:

• Get next node from the queue
• Swap its left and right child nodes
• Push its left and right children into the queue

O(n).

Auxiliary Space Used

O(n).

We are using a queue for storing nodes to do BFS traversal over the tree. In the worst case scenario, queue size will be `n`.

Space Complexity

O(n).

Input is O(n) because we are storing `n` nodes relationships and each relationship occupies O(1) space and auxiliary space used is O(n). So, O(n) + O(n) = O(n).

Code For Mirror Image Of Binary Tree Solution 2: Breadth First Search

``````    /*
* Asymptotic complexity in terms of number of nodes \`n\` in the given tree:
* Time: O(n).
* Auxiliary space: O(n).
* Total space: O(n).
*/

public static void mirror_image(BinaryTreeNode root) {
if (root == null)
return;

// Do BFS. While doing BFS, keep swapping
// left and right children
while(!queue.isEmpty()) {
// Pop top node from queue.
BinaryTreeNode cur_node = queue.poll();

// Swap left child with right child.
BinaryTreeNode temp = cur_node.left;
cur_node.left = cur_node.right;
cur_node.right = temp;

// Push left and right children.
if (cur_node.left != null)
if (cur_node.right != null)
}
}
``````

We hope that these solutions to creating a mirror image of a binary tree have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 17 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as: