Binary TreesProblem 5 of 35
Mirror of a tree
Problem Statement
Given a binary tree, convert it to its mirror (also called invert binary tree). In a mirror tree, all left and right children are swapped.
Example:
Original: Mirror:
1 1
/ \ / \
2 3 3 2
/ \ / \
4 5 5 4
- Input: Root of original tree
- Output: Root of mirror tree
Approach 1: Brute Force (Using Queue - Level Order)
Intuition
Use level order traversal. At each node, swap its left and right children.
Algorithm
- Use a queue for BFS traversal
- For each node, swap its left and right children
- Add children to queue for processing
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode mirrorBFS(TreeNode root) {
if (root == null) return null;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
// Swap left and right children
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
return root;
}
}Complexity Analysis
- Time Complexity: O(n) - Visit each node once
- Space Complexity: O(n) - Queue can hold up to n/2 nodes
Approach 2: Optimal (DFS - Recursion)
Intuition
Recursively mirror left and right subtrees, then swap them. This is elegant and requires minimal code.
Algorithm
- Base case: if node is null, return null
- Recursively mirror left subtree
- Recursively mirror right subtree
- Swap the mirrored subtrees
- Return the node
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode mirror(TreeNode root) {
if (root == null) {
return null;
}
// Recursively mirror subtrees
TreeNode left = mirror(root.left);
TreeNode right = mirror(root.right);
// Swap left and right
root.left = right;
root.right = left;
return root;
}
// Alternative: More concise version
public TreeNode mirrorConcise(TreeNode root) {
if (root == null) return null;
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
mirrorConcise(root.left);
mirrorConcise(root.right);
return root;
}
}Complexity Analysis
- Time Complexity: O(n) - Visit each node exactly once
- Space Complexity: O(h) - Recursion stack depth, where h is height
Bonus: Check if Two Trees are Mirrors
Key Takeaways
- Simple swap operation at each node converts tree to its mirror
- Both DFS and BFS approaches work equally well
- The recursive approach is more elegant and easier to understand
- Mirroring is its own inverse - mirroring twice returns original tree
- This is a popular interview question (Invert Binary Tree - Leetcode #226)