Mirror a Binary Tree in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after mirroring a simple binary tree

What is the output of the in-order traversal after mirroring the binary tree?

DSA Java

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

public class MirrorTree {
    public static void mirror(Node root) {
        if (root == null) return;
        Node temp = root.left;
        root.left = root.right;
        root.right = temp;
        mirror(root.left);
        mirror(root.right);
    }

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

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

        mirror(root);
        inorder(root);
    }
}

A 3 1 5 2 4

B 4 2 5 1 3

C 5 3 4 2 1

D 1 2 4 5 3

💡 Hint

Remember that mirroring swaps left and right children at every node.

The original tree in-order is 4 2 5 1 3. After mirroring, left and right children swap, so in-order becomes 3 1 5 2 4.

❓ Predict Output

intermediate

Output of pre-order traversal after mirroring

What is the output of the pre-order traversal after mirroring the binary tree below? Tree: 10 / \ 20 30 / / \ 40 50 60

DSA Java

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

public class MirrorTree {
    public static void mirror(Node root) {
        if (root == null) return;
        Node temp = root.left;
        root.left = root.right;
        root.right = temp;
        mirror(root.left);
        mirror(root.right);
    }

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

    public static void main(String[] args) {
        Node root = new Node(10);
        root.left = new Node(20);
        root.right = new Node(30);
        root.left.left = new Node(40);
        root.right.left = new Node(50);
        root.right.right = new Node(60);

        mirror(root);
        preorder(root);
    }
}

A 10 20 30 40 50 60

B 10 20 40 30 50 60

C 10 30 60 50 20 40

D 10 30 50 60 20 40

💡 Hint

Pre-order visits root, then left subtree, then right subtree after mirroring.

Mirroring swaps left and right children. Original pre-order is 10 20 40 30 50 60. After mirroring, left and right children swap, so pre-order becomes 10 30 60 50 20 40.

🔧 Debug

advanced

Identify the bug in the mirror function

The following mirror function is intended to mirror a binary tree. What is the bug that causes incorrect mirroring?

DSA Java

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

A Swapping children before recursive calls is incorrect; should swap after.

B Missing base case for leaf nodes causes infinite recursion.

C The function does not swap children at all.

D Swapping children after recursive calls causes incorrect mirroring order.

💡 Hint

Think about when children are swapped relative to recursion.

Swapping children after recursive calls means recursion works on original children, not swapped ones, causing incorrect mirror.

🧠 Conceptual

advanced

Time complexity of mirroring a binary tree

What is the time complexity of the mirror function that recursively swaps left and right children of every node in a binary tree with n nodes?

A O(log n), because recursion depth is log n.

B O(n), because each node is visited once.

C O(n log n), because each swap takes log n time.

D O(n^2), because each node swaps with all others.

💡 Hint

Consider how many nodes the function visits and how much work per node.

The mirror function visits each node once and swaps children in constant time, so total time is O(n).

🚀 Application

expert

Mirror a binary tree iteratively

Which of the following Java code snippets correctly mirrors a binary tree using an iterative approach with a queue?

DSA Java

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

public class MirrorTreeIterative {
    public static void mirror(Node root) {
        // Fill in the correct iterative mirroring code
    }
}

A

if (root == null) return;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
    Node current = queue.poll();
    Node temp = current.left;
    current.left = current.right;
    current.right = temp;
    if (current.left != null) queue.add(current.left);
    if (current.right != null) queue.add(current.right);
}

B

if (root == null) return;
Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
    Node current = stack.pop();
    Node temp = current.left;
    current.left = current.right;
    current.right = temp;
    if (current.left != null) stack.push(current.left);
    if (current.right != null) stack.push(current.right);
}

C

if (root == null) return;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
    Node current = queue.poll();
    if (current.left != null) queue.add(current.left);
    if (current.right != null) queue.add(current.right);
    Node temp = current.left;
    current.left = current.right;
    current.right = temp;
}

D

if (root == null) return;
Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
    Node current = stack.pop();
    if (current.left != null) stack.push(current.left);
    if (current.right != null) stack.push(current.right);
    Node temp = current.left;
    current.left = current.right;
    current.right = temp;
}

💡 Hint

Use a queue for level order traversal and swap children immediately after dequeue.

Option A uses a queue for breadth-first traversal and swaps children immediately, correctly mirroring the tree iteratively.

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