Mirror a Binary Tree in DSA Java - Deep Dive

Overview - Mirror a Binary Tree

What is it?

Mirroring a binary tree means creating a new tree that is the exact reverse of the original. Every left child becomes a right child, and every right child becomes a left child. This operation flips the tree around its center. It helps us understand tree structures and transformations.

Why it matters

Without the ability to mirror a binary tree, we would struggle to easily reverse tree structures or compare symmetric properties. Mirroring helps in problems like checking if two trees are mirror images or in graphical transformations. It also deepens understanding of tree traversal and manipulation.

Where it fits

Before learning to mirror a binary tree, you should understand what a binary tree is and how to traverse it (like preorder, inorder, postorder). After mastering mirroring, you can explore tree symmetry checks, tree rotations, and advanced tree algorithms.

Mental Model

Core Idea

Mirroring a binary tree swaps every left and right child recursively, flipping the tree around its center.

Think of it like...

Imagine holding a family photo and flipping it horizontally so that everyone on the left moves to the right and vice versa, but the people themselves stay the same.

Original Tree:           Mirrored Tree:
    1                          1
   / \                        / \
  2   3                      3   2
 / \  /                     /   / \
4  5 6                     6   5  4

Build-Up - 7 Steps

1

Foundation

Understanding Binary Tree Structure

Concept: Learn what a binary tree is and how nodes connect with left and right children.

A binary tree is a structure where each node has up to two children: left and right. Each node holds a value and pointers to its children or null if none. For example, node 1 can have left child 2 and right child 3.

Result

You can visualize and represent a tree with nodes connected left and right.

Understanding the basic structure of a binary tree is essential before changing or manipulating it.

2

Foundation

Traversing a Binary Tree

Concept: Learn how to visit each node in a tree using preorder traversal.

Preorder traversal visits the current node first, then the left subtree, then the right subtree. For example, for tree with root 1, left 2, right 3, preorder visits nodes in order: 1, 2, 3.

Result

You can list nodes in a specific order to understand tree shape.

Traversal is the foundation for any tree operation, including mirroring.

3

Intermediate

Swapping Left and Right Children

🤔Before reading on: do you think swapping children at one node affects the whole tree or just that node? Commit to your answer.

Concept: Mirroring involves swapping left and right children at every node recursively.

At each node, swap its left and right child pointers. Then repeat this process for each child node. This flips the tree around its center.

Result

Each node's children are reversed, changing the tree's shape.

Knowing that mirroring is a recursive swap helps you understand the process applies to the entire tree, not just one node.

4

Intermediate

Implementing Mirror Function Recursively

🤔Before reading on: do you think the mirror function should return a new tree or modify the original? Commit to your answer.

Concept: Write a function that swaps children recursively and modifies the original tree in place.

In Java, define a method mirror(TreeNode root). If root is null, return. Otherwise, swap root.left and root.right, then call mirror on both children. Code: public void mirror(TreeNode root) { if (root == null) return; TreeNode temp = root.left; root.left = root.right; root.right = temp; mirror(root.left); mirror(root.right); }

Result

The original tree is flipped in place, no new tree created.

Modifying the tree in place is efficient and common in practice, avoiding extra memory use.

5

Intermediate

Dry Run of Mirror on Sample Tree

🤔Before reading on: after mirroring, where will the original leftmost leaf node appear? Commit to your answer.

Concept: Trace the mirror function step-by-step on a small tree to see how nodes move.

Given tree: 1 / \ 2 3 / 4 Step 1: At node 1, swap left(2) and right(3). Step 2: Mirror left subtree (originally 3), which has no children. Step 3: Mirror right subtree (originally 2). Step 4: At node 2, swap left(4) and right(null). Step 5: Mirror left subtree (null) and right subtree (4). Step 6: Node 4 has no children, return. Resulting tree: 1 / \ 3 2 \ 4

Result

The tree is flipped, leftmost leaf 4 moves to rightmost position.

Tracing the function helps understand recursion and how each node's children swap affects the whole tree.

6

Advanced

Iterative Mirror Using Stack

🤔Before reading on: do you think mirroring can be done without recursion? Commit to your answer.

Concept: Use a stack to traverse nodes and swap children iteratively.

Instead of recursion, use a stack to hold nodes. While stack not empty, pop node, swap children, then push children to stack. Code: public void mirrorIterative(TreeNode root) { if (root == null) return; Stack stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode current = stack.pop(); TreeNode 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); } }

Result

The tree is mirrored without recursion, using explicit stack.

Knowing iterative methods helps avoid stack overflow in deep trees and shows alternative approaches.

7

Expert

Mirror Impact on Tree Properties and Uses

🤔Before reading on: does mirroring a binary search tree keep it a valid BST? Commit to your answer.

Concept: Mirroring changes tree structure but can break properties like BST ordering; understand implications.

Mirroring swaps children but does not reorder values. For BSTs, this breaks the ordering property, so mirrored tree is not a BST. However, mirroring is useful for checking symmetry or creating visual effects. In production, mirroring is used in graphics, expression trees, and symmetric checks.

Result

Mirroring changes shape but may break special tree properties.

Understanding how mirroring affects tree properties prevents misuse and guides correct application.

Under the Hood

Mirroring works by recursively visiting each node and swapping its left and right child pointers. This process uses the call stack to remember nodes yet to be processed. Each swap changes the tree's shape locally, and recursion ensures the entire tree is covered. In iterative versions, an explicit stack replaces the call stack.

Why designed this way?

Recursion naturally fits tree structures because trees are defined recursively. Swapping children at each node is a simple, local operation that collectively flips the whole tree. Alternatives like creating a new mirrored tree exist but use more memory. The in-place swap is efficient and intuitive.

┌─────────────┐
│   Start     │
└──────┬──────┘
       │
       ▼
┌─────────────┐
│ Visit Node  │
└──────┬──────┘
       │
       ▼
┌─────────────┐
│ Swap Left & │
│ Right Child │
└──────┬──────┘
       │
       ▼
┌─────────────┐
│ Recurse on  │
│ Left Child  │
└──────┬──────┘
       │
       ▼
┌─────────────┐
│ Recurse on  │
│ Right Child │
└─────────────┘

Myth Busters - 3 Common Misconceptions

Quick: Does mirroring a binary search tree keep it a valid BST? Commit to yes or no.

Common Belief: Mirroring a binary search tree keeps it a valid BST because values don't change.

Reality: Mirroring swaps children but does not reorder values, so the BST property is broken after mirroring.

Why it matters: Assuming the BST property holds after mirroring can cause incorrect search results and bugs.

Quick: Does mirroring create a new tree or modify the original? Commit to your answer.

Common Belief: Mirroring always creates a new mirrored tree, leaving the original unchanged.

Reality: Most mirror implementations modify the original tree in place by swapping children.

Why it matters: Expecting a new tree wastes memory or causes confusion about which tree is used after mirroring.

Quick: Is mirroring the same as rotating a tree? Commit to yes or no.

Common Belief: Mirroring a tree is the same as rotating it left or right.

Reality: Mirroring flips the tree horizontally by swapping children at every node, while rotation changes structure locally to balance or reorder the tree.

Why it matters: Confusing mirroring with rotation leads to wrong tree transformations and algorithm errors.

Expert Zone

1

Mirroring a tree in place is efficient but destroys original structure; cloning before mirroring is needed if original must be preserved.

2

In threaded binary trees or trees with parent pointers, mirroring requires careful updates to maintain all links correctly.

3

Mirroring can be combined with traversal orders to solve complex problems like symmetric tree checks or expression tree transformations.

When NOT to use

Avoid mirroring when the tree's ordering or balancing properties must be preserved, such as in binary search trees or AVL trees. Instead, use rotations or rebuild the tree. Mirroring is also not suitable when the tree is immutable or shared across threads without copying.

Production Patterns

Mirroring is used in graphical applications to flip scene graphs, in compilers to transform expression trees, and in algorithms to check if two trees are mirror images. It also appears in interview problems testing recursion and tree manipulation skills.

Connections

Tree Traversals

Mirroring builds on recursive tree traversal patterns like preorder and postorder.

Understanding traversal orders helps implement mirroring correctly and efficiently.

Symmetric Tree Check

Mirroring is closely related to checking if two trees are mirror images of each other.

Knowing how to mirror a tree helps solve symmetry problems by comparing a tree to the mirror of another.

Image Processing

Mirroring a binary tree is conceptually similar to flipping an image horizontally.

Recognizing this connection helps understand mirroring as a spatial transformation beyond data structures.

Common Pitfalls

#1 Trying to mirror a null tree without checking for null causes errors.

Wrong approach:

public void mirror(TreeNode root) {
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
mirror(root.left);
mirror(root.right);
}

Correct approach:

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

Root cause:

Not checking for null before accessing node children leads to null pointer exceptions.

#2 Assuming mirroring creates a new tree and returning a new root without modifying original.

Wrong approach:

public TreeNode mirror(TreeNode root) {
if (root == null) return null;
TreeNode left = mirror(root.left);
TreeNode right = mirror(root.right);
TreeNode newRoot = new TreeNode(root.val);
newRoot.left = right;
newRoot.right = left;
return newRoot;
}
// But original tree remains unchanged and caller ignores returned tree.

Correct approach:

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

Root cause:

Confusing in-place modification with creating a new tree leads to inconsistent usage.

#3 Using mirroring to fix a binary search tree ordering problem.

Wrong approach:

// Trying to fix BST by mirroring
mirror(root);
// Then expecting BST properties to hold

Correct approach:

// Use rotations or rebuild tree to fix BST
// Mirroring is not for ordering fixes

Root cause:

Misunderstanding that mirroring changes structure but not node values or ordering.

Key Takeaways

Mirroring a binary tree flips it by swapping left and right children at every node recursively.

This operation modifies the original tree in place, making it memory efficient but destructive.

Mirroring breaks special tree properties like binary search tree ordering, so use it carefully.

Both recursive and iterative methods exist; recursion fits naturally but iteration avoids stack overflow.

Understanding mirroring deepens knowledge of tree traversal, recursion, and tree transformations.

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