Mirror a Binary Tree in DSA C# - Deep Dive

Overview - Mirror a Binary Tree

What is it?

Mirroring a binary tree means creating a new tree where the left and right children of all nodes are swapped. Imagine flipping the tree as if looking at it in a mirror. This operation changes the structure but keeps the values intact, just rearranged in a reversed way. It helps us understand tree transformations and is a common problem in computer science.

Why it matters

Mirroring a binary tree helps in understanding how trees can be manipulated and transformed. Without this concept, we would struggle to reverse tree structures or solve problems that require symmetrical operations. It also forms the basis for more complex tree algorithms and visualizations, impacting areas like graphics, data organization, and searching.

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, and postorder). After mastering mirroring, you can explore tree rotations, balancing trees, and advanced tree algorithms like AVL or Red-Black trees.

Mental Model

Core Idea

Mirroring a binary tree means swapping every node's left and right children recursively to create a reversed structure.

Think of it like...

It's like looking at a family tree photo in a mirror where every branch flips sides, but the people and connections remain the same.

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

Build-Up - 6 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, a node with value 1 can have left child 2 and right child 3.

Result

You can visualize and represent a binary tree with nodes and their left/right links.

Understanding the basic structure of binary trees is essential before performing any operations like mirroring.

2

Foundation

Traversing a Binary Tree

Concept: Learn how to visit nodes in a binary 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 child 2, right child 3, preorder visits nodes in order: 1, 2, 3.

Result

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

Traversal is key to accessing and modifying nodes systematically during mirroring.

3

Intermediate

Swapping Left and Right Children

Concept: Introduce the idea of swapping the left and right children of a node.

At any node, you can swap its left and right children pointers. For example, if a node has left child 2 and right child 3, after swapping, left child becomes 3 and right child becomes 2.

Result

The subtree rooted at that node is flipped horizontally.

Swapping children is the core operation that changes the tree's shape to its mirror.

4

Intermediate

Recursive Mirroring of Subtrees

🤔Before reading on: do you think mirroring a tree requires swapping children only at the root or at every node? Commit to your answer.

Concept: Mirroring requires recursively swapping children at every node in the tree.

To mirror the whole tree, start at the root, swap its children, then recursively mirror the left and right subtrees. This ensures every part of the tree is flipped.

Result

The entire tree structure is reversed, not just the top node.

Understanding recursion here is crucial because the mirror operation applies at every node, not just once.

5

Advanced

Implementing Mirror Function in C#

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

Concept: Implement a function that modifies the existing tree by swapping children recursively.

public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { this.val = val; this.left = left; this.right = right; } } public class Solution { public void Mirror(TreeNode root) { if (root == null) return; // Swap children TreeNode temp = root.left; root.left = root.right; root.right = temp; // Recursively mirror subtrees Mirror(root.left); Mirror(root.right); } }

Result

The input tree is modified in place to its mirror image.

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

6

Expert

Handling Edge Cases and Performance

🤔Before reading on: do you think mirroring an empty tree or a single-node tree changes anything? Commit to your answer.

Concept: Consider edge cases like empty trees and analyze time complexity.

If the tree is empty (null), the function returns immediately. For a single-node tree, swapping children has no effect. The time complexity is O(n) because each node is visited once. The space complexity depends on recursion stack depth, O(h), where h is tree height.

Result

The mirror function safely handles all tree shapes and runs efficiently.

Recognizing edge cases prevents bugs, and understanding complexity helps optimize for large trees.

Under the Hood

The mirror function works by recursively visiting each node in the tree. At each node, it swaps the pointers to the left and right children. This swapping changes the direction of the branches. The recursion ensures that this swap happens at every node, effectively flipping the entire tree horizontally. The call stack keeps track of nodes to visit next, unwinding after reaching leaf nodes.

Why designed this way?

Recursion naturally fits tree structures because trees are defined recursively (each subtree is a tree). Swapping pointers in place avoids extra memory use and keeps the operation simple. Alternatives like creating a new mirrored tree would require extra space and copying nodes, which is less efficient.

Mirror Function Flow:

  [Root Node]
      |
  Swap left <--> right
      |
  /           \
Mirror(left)  Mirror(right)
      |           |
    ...         ...

Recursion continues until leaf nodes (null) are reached.

Myth Busters - 4 Common Misconceptions

Quick: Does mirroring a binary tree change the node values? Commit to yes or no.

Common Belief: Mirroring a binary tree changes the values of the nodes to their opposites or some new values.

Reality: Mirroring only swaps the positions of nodes; the values inside nodes remain exactly the same.

Why it matters: If you expect values to change, you might incorrectly modify or lose data during mirroring.

Quick: Is it enough to swap children only at the root to mirror the whole tree? Commit to yes or no.

Common Belief: Swapping the left and right children of the root node alone mirrors the entire tree.

Reality: You must swap children at every node recursively; swapping only the root swaps just the top level.

Why it matters: Partial swapping leads to incorrect tree structure and bugs in algorithms relying on full mirroring.

Quick: Does mirroring a binary tree always require creating a new tree? Commit to yes or no.

Common Belief: Mirroring requires building a new tree with nodes copied in reversed order.

Reality: Mirroring can be done in place by swapping pointers without creating new nodes.

Why it matters: Thinking a new tree is needed wastes memory and complicates the solution unnecessarily.

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

Common Belief: Mirroring a binary search tree (BST) keeps it a valid BST.

Reality: Mirroring a BST usually breaks the BST property because left and right children are swapped.

Why it matters: Assuming the BST property holds after mirroring can cause incorrect search results or data corruption.

Expert Zone

1

Mirroring a tree in place is efficient but irreversible unless you mirror again; this can be used to toggle views.

2

The recursion stack depth equals the tree height, so very unbalanced trees can cause stack overflow; iterative approaches can mitigate this.

3

Mirroring is a special case of tree isomorphism transformations and can be combined with other tree operations for complex algorithms.

When NOT to use

Avoid in-place mirroring when the original tree structure must be preserved; instead, create a new mirrored copy. Also, do not mirror binary search trees if you need to maintain search properties; consider tree rotations or balanced tree algorithms instead.

Production Patterns

Mirroring is used in graphics to flip scene graphs, in UI frameworks to support right-to-left layouts, and in algorithms that require symmetrical tree processing. It also appears in interview questions to test understanding of recursion and tree manipulation.

Connections

Tree Traversals

Mirroring builds on tree traversal techniques by visiting nodes recursively.

Knowing traversal methods helps understand how to systematically access and modify every node during mirroring.

Graph Isomorphism

Mirroring is a form of graph transformation that preserves node values but changes edge directions.

Understanding mirroring deepens insight into how graphs and trees can be transformed while preserving some properties.

Symmetry in Art and Design

Mirroring a tree is analogous to creating symmetrical patterns in art by flipping shapes.

Recognizing symmetry in nature and art helps appreciate why mirroring is a fundamental operation in computer science and design.

Common Pitfalls

#1 Trying to mirror the tree by swapping values instead of swapping child pointers.

Wrong approach:

void Mirror(TreeNode root) {
if (root == null) return;
int temp = root.val;
root.val = root.right.val; // Error if right is null
root.right.val = temp;
Mirror(root.left);
Mirror(root.right);
}

Correct approach:

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 node value swapping with pointer swapping; mirroring requires changing structure, not values.

#2 Not handling null nodes before swapping children, causing runtime errors.

Wrong approach:

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

Correct approach:

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:

Missing base case for recursion leads to null reference exceptions.

#3 Assuming mirroring preserves binary search tree properties.

Wrong approach:

Mirror(bstRoot);
// Then perform BST operations assuming tree is still valid

Correct approach:

// Do not mirror BST if you need to keep BST properties
// Instead, use tree rotations or rebuild tree

Root cause:

Misunderstanding that swapping children changes node ordering critical for BST.

Key Takeaways

Mirroring a binary tree means swapping left and right children at every node recursively.

This operation changes the tree's shape but keeps node values unchanged.

Recursion is the natural and efficient way to visit and swap all nodes in the tree.

Mirroring can be done in place without creating new nodes, saving memory.

Mirroring a binary search tree breaks its ordering property, so use with caution.

Practice

1. What does mirroring a binary tree mean?

easy

A. Swapping the left and right children of every node

B. Removing all leaf nodes

C. Sorting the nodes in ascending order

D. Counting the total number of nodes

Solution

1. Step 1: Understand the mirror operation

   Mirroring means swapping left and right children at every node in the tree.

2. Step 2: Identify the effect on the tree

   This operation flips the tree horizontally, creating a mirror image.

3. Final Answer:

   Swapping the left and right children of every node -> Option A

4. Quick Check:

   Mirror = Swap children [OK]

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

Common Mistakes:

• Thinking mirror means sorting nodes
• Confusing mirror with deleting nodes
• Assuming mirror counts nodes

2. Which of the following C# method signatures correctly represents a recursive function to mirror a binary tree node named root?

easy

A. void MirrorTree(Node root)

B. int MirrorTree(Node root)

C. Node MirrorTree(Node root)

D. bool MirrorTree(Node root)

Solution

1. Step 1: Understand the purpose of the function

   The function modifies the tree in place and does not need to return a value.

2. Step 2: Choose the correct return type

   Since it changes the tree nodes directly, the return type should be void.

3. Final Answer:

   void MirrorTree(Node root) -> Option A

4. Quick Check:

   In-place change means void return [OK]

Hint: Mirror function usually returns void as it modifies tree directly [OK]

Common Mistakes:

• Returning int or bool unnecessarily
• Returning Node when not needed
• Using incorrect parameter types

3. Given the following binary tree and the C# code to mirror it, what will be the output of the inorder traversal after mirroring?

    1
   / \
  2   3
 /     \
4       5

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

// Inorder traversal prints nodes in order: left, root, right

medium

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

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

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

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

Solution

1. Step 1: Mirror the tree structure

   Swap left and right children at every node:
   Original root 1: left=2, right=3 -> after mirror left=3, right=2
   Node 2: left=4, right=null -> after mirror left=null, right=4
   Node 3: left=null, right=5 -> after mirror left=5, right=null

2. Step 2: Perform inorder traversal on mirrored tree

   Inorder = left, root, right
   Start at root (1):
   Left subtree (3): left=5, right=null -> inorder: 5,3
   Root: 1
   Right subtree (2): left=null, right=4 -> inorder: 2,4
   Combined inorder: [5, 3, 1, 2, 4]

3. Final Answer:

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

4. Quick Check:

   Mirror + inorder = [5,3,1,2,4] [OK]

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

Common Mistakes:

• Not swapping children correctly
• Confusing preorder with inorder traversal
• Forgetting to mirror all nodes

4. The following C# code attempts to mirror a binary tree but does not work correctly. What is the main error?

void MirrorTree(Node root) {
  MirrorTree(root.left);
  MirrorTree(root.right);
  var temp = root.left;
  root.left = root.right;
  root.right = temp;
}

medium

A. Swapping children happens after recursive calls, causing incorrect mirror

B. Missing base case for null root

C. Using var instead of explicit type causes error

D. Function should return Node instead of void

Solution

1. Step 1: Analyze the base case

   The code lacks an if (root == null) return; check before recursing on children.

2. Step 2: Understand why this causes error

   Recursing on null children leads to NullReferenceException or stack overflow since there's no termination condition.

3. Final Answer:

   Missing base case for null root -> Option B

4. Quick Check:

   Recursion needs if(root == null) return; [OK]

Hint: Always include null base case in tree recursion [OK]

Common Mistakes:

• Omitting base case for null nodes
• Swapping after recursion instead of before
• Thinking var causes error

5. You have a binary tree where some nodes have only one child (either left or right). You want to mirror this tree using C#. Which approach correctly handles all cases including nodes with single children?

hard

A. Mirror by creating a new tree instead of modifying original

B. Only swap children if both left and right children exist

C. Swap children only at leaf nodes

D. Recursively swap left and right children if node is not null, then recurse on both children

Solution

1. Step 1: Consider nodes with single child

   Nodes with only one child still need swapping; swapping null with a child is valid.

2. Step 2: Choose recursive approach that swaps and recurses regardless of child presence

   Swapping children even if one is null ensures correct mirror. Then recurse on both children to continue mirroring.

3. Final Answer:

   Recursively swap left and right children if node is not null, then recurse on both children -> Option D

4. Quick Check:

   Swap children always, recurse both sides [OK]

Hint: Always swap children even if one is null, then recurse [OK]

Common Mistakes:

• Skipping swap when one child is null
• Swapping only leaf nodes
• Creating new tree unnecessarily