Mirror a Binary Tree in DSA Java

Mental Model

Flipping a binary tree means swapping every left child with its right child, making the tree look like its reflection in a mirror.

Analogy: Imagine holding a tree-shaped paper cutout in front of a mirror; the mirror image swaps left and right branches exactly.

    1
   / \
  2   3
 / \ / \
4  5 6  7

Mirror swaps left and right children at every node.

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2 and right child 3; 2 has children 4 and 5; 3 has children 6 and 7

Goal: Transform the tree so that left and right children of every node are swapped, producing the mirror image

Step 1: Start at root node 1, swap its left and right children

    1
   / \
  3   2
 / \ / \
6  7 4  5

Why: Swapping children at root begins the mirroring process

Step 2: Move to left child (originally right child) node 3, swap its children 6 and 7

    1
   / \
  3   2
 / \ / \
7  6 4  5

Why: Swapping children at node 3 continues mirroring left subtree

Step 3: Move to right child (originally left child) node 2, swap its children 4 and 5

    1
   / \
  3   2
 / \ / \
7  6 5  4

Why: Swapping children at node 2 completes mirroring right subtree

Step 4: Recursively apply swaps to leaf nodes 7, 6, 5, 4 which have no children

    1
   / \
  3   2
 / \ / \
7  6 5  4

Why: Leaf nodes have no children, so no swaps needed; recursion ends

Result:

    1
   / \
  3   2
 / \ / \
7  6 5  4

This is the mirrored binary tree.

Annotated Code

DSA Java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class MirrorBinaryTree {
    public static void mirror(TreeNode root) {
        if (root == null) return; // base case: empty node
        // swap left and right children
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        // recursively mirror left subtree
        mirror(root.left);
        // recursively mirror right subtree
        mirror(root.right);
    }

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

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

        mirror(root);
        printTree(root);
    }
}

if (root == null) return; // base case: empty node

stop recursion when node is empty

TreeNode temp = root.left; root.left = root.right; root.right = temp;

swap left and right children of current node

mirror(root.left);

recursively mirror left subtree (originally right subtree after swap)

mirror(root.right);

recursively mirror right subtree (originally left subtree after swap)

Output

1 3 7 6 2 5 4 

Complexity Analysis

Time: O(n) because every node in the tree is visited once to swap children

Space: O(h) where h is the height of the tree due to recursion stack

vs Alternative: This recursive approach is simpler and more intuitive than iterative methods which require explicit stacks or queues

Edge Cases

Empty tree (root is null)

Function returns immediately without error

DSA Java

if (root == null) return; // base case: empty node

Tree with only one node

No swaps happen, function returns after base case checks

DSA Java

if (root == null) return; // base case: empty node

Tree with only left or only right children

Swapping children still works correctly, mirroring the structure

DSA Java

TreeNode temp = root.left;
root.left = root.right;
root.right = temp;

When to Use This Pattern

When a problem asks to flip or reflect a binary tree structure, use the mirror pattern by swapping left and right children recursively.

Common Mistakes

Mistake: Swapping children but forgetting to recursively mirror subtrees
Fix: Add recursive calls to mirror both left and right children after swapping

Mistake: Not handling null nodes leading to null pointer errors
Fix: Add base case to return immediately if current node is null

Summary

It flips a binary tree by swapping left and right children at every node.

Use it when you need the mirror image of a binary tree.

The key is to swap children and then recursively apply the same to subtrees.

Practice

1. What does it mean to mirror a binary tree?

easy

A. Remove all leaf nodes from the tree

B. Swap the left and right children of every node in the tree

C. Convert the tree into a linked list

D. Sort the nodes in ascending order

Solution

1. Step 1: Understand the mirror operation

   Mirroring a binary tree means swapping the left and right children of every node.

2. Step 2: Apply the definition to the tree

   By swapping children at every node, the tree becomes a mirror image of the original.

3. Final Answer:

   Swap the left and right children of every node in the tree -> Option B

4. Quick Check:

   Mirror = Swap children [OK]

Hint: Mirror means swap left and right children at all nodes [OK]

Common Mistakes:

• Thinking mirror means deleting nodes
• Confusing mirror with sorting
• Assuming mirror flattens the tree

2. Which of the following Java method signatures correctly represents a function to mirror a binary tree node?

easy

A. public void mirrorTree(Node root)

B. public int mirrorTree(Node root)

C. void mirrorTree(Node root) throws Exception

D. public Node mirrorTree()

Solution

1. Step 1: Identify correct return type

   Mirroring modifies the tree in place, so void return type is appropriate.

2. Step 2: Check method parameters

   The method should accept the root node to start mirroring from.

3. Final Answer:

   public void mirrorTree(Node root) -> Option A

4. Quick Check:

   Void return + root parameter = correct signature [OK]

Hint: Mirror modifies tree in place, so use void with root parameter [OK]

Common Mistakes:

• Using return type int instead of void
• Missing root parameter
• Adding unnecessary exceptions

3. Given the following binary tree and the mirror function below, what will be the preorder traversal output after mirroring?

    1
   / \
  2   3
 /     \
4       5

void mirrorTree(Node root) {
  if (root == null) return;
  Node temp = root.left;
  root.left = root.right;
  root.right = temp;
  mirrorTree(root.left);
  mirrorTree(root.right);
}

medium

A. [1, 3, 5, 2, 4]

B. [1, 2, 4, 3, 5]

C. [1, 3, 2, 5, 4]

D. [1, 5, 3, 4, 2]

Solution

1. Step 1: Understand the mirror function

   The function swaps left and right children at every node recursively.

2. Step 2: Apply mirror to the tree

   Original tree preorder: 1,2,4,3,5. After mirror, left and right children swap: - Root 1: left=3, right=2 - Node 3: left=5, right=null - Node 2: left=null, right=4

3. Step 3: Preorder traversal after mirror

   Visit root, then left subtree, then right subtree: 1, 3, 5, 2, 4

4. Final Answer:

   [1, 3, 5, 2, 4] -> Option A

5. Quick Check:

   Mirror swaps children; preorder = [1,3,5,2,4] [OK]

Hint: Mirror swaps children; preorder visits root-left-right [OK]

Common Mistakes:

• Not swapping children correctly
• Confusing preorder with inorder
• Missing recursive calls

4. The following code attempts to mirror a binary tree but causes a NullPointerException. What is the error?

public void mirrorTree(Node root) {
  Node temp = root.left;
  root.left = root.right;
  root.right = temp;
  mirrorTree(root.left);
  mirrorTree(root.right);
}

medium

A. Swapping left and right children incorrectly

B. Recursive calls should be after swapping

C. Missing null check before accessing root.left

D. Method should return a Node instead of void

Solution

1. Step 1: Identify cause of NullPointerException

   The code accesses root.left without checking if root is null.

2. Step 2: Fix by adding null check

   Adding "if (root == null) return;" at the start prevents errors when root is null.

3. Final Answer:

   Missing null check before accessing root.left -> Option C

4. Quick Check:

   NullPointerException = missing null check [OK]

Hint: Always check if node is null before accessing children [OK]

Common Mistakes:

• Ignoring null checks
• Thinking swap order causes error
• Changing return type unnecessarily

5. You have a binary tree where some nodes have only one child. After mirroring the tree using the standard mirror function, which of the following statements is true about the structure of the mirrored tree?

hard

A. Leaf nodes become internal nodes after mirroring

B. Nodes with one child will have two children after mirroring

C. The tree height will always increase by 1

D. Nodes with only left child will have only right child after mirroring

Solution

1. Step 1: Understand mirroring effect on children

   Mirroring swaps left and right children at every node.

2. Step 2: Analyze nodes with one child

   If a node has only a left child, after mirroring it will have only a right child (the left child moves to right).

3. Step 3: Check other options

   Tree height does not necessarily increase; leaf nodes remain leaves; nodes do not gain extra children.

4. Final Answer:

   Nodes with only left child will have only right child after mirroring -> Option D

5. Quick Check:

   Mirror swaps children, so left-only becomes right-only [OK]

Hint: Mirror swaps children, so single left child becomes single right child [OK]

Common Mistakes:

• Assuming tree height changes
• Thinking nodes gain extra children
• Confusing leaf and internal nodes