Mirror a Binary Tree in DSA C#

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

Mirror:
    1
   / \
  3   2
  \  / \
   6 5  4

Dry Run Walkthrough

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

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

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

    1
   / \
  3   2
  \     / \
   6   4   5

Why: Swapping children at root begins the mirroring process

Step 2: Move to left child 3, swap its children (only right child 6 becomes left child)

    1
   / \
  3   2
  \     / \
   6   4   5

Why: Mirroring subtree rooted at 3 swaps its children

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

    1
   / \
  3   2
  \     / \
   6   5   4

Why: Mirroring subtree rooted at 2 completes the mirror

Step 4: Leaf nodes 6, 5, 4 have no children to swap, recursion ends

    1
   / \
  3   2
  \     / \
   6   5   4

Why: Leaves have no children, so no further swaps needed

Result:

    1
   / \
  3   2
  \     / \
   6   5   4

Annotated Code

DSA C#

using System;

class Node
{
    public int data;
    public Node left, right;

    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}

class BinaryTree
{
    public Node root;

    // Function to mirror the binary tree
    public void Mirror(Node node)
    {
        if (node == null) return; // base case: empty node

        // swap left and right children
        Node temp = node.left;
        node.left = node.right;
        node.right = temp;

        // recursively mirror left subtree
        Mirror(node.left);

        // recursively mirror right subtree
        Mirror(node.right);
    }

    // Helper to print tree inorder for verification
    public void InorderPrint(Node node)
    {
        if (node == null) return;
        InorderPrint(node.left);
        Console.Write(node.data + " ");
        InorderPrint(node.right);
    }

    static void Main(string[] args)
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.root.right.right = new Node(6);

        Console.WriteLine("Original inorder traversal:");
        tree.InorderPrint(tree.root);
        Console.WriteLine();

        tree.Mirror(tree.root);

        Console.WriteLine("Inorder traversal after mirroring:");
        tree.InorderPrint(tree.root);
        Console.WriteLine();
    }
}

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

stop recursion when node is empty

Node temp = node.left; node.left = node.right; node.right = temp;

swap left and right children of current node

Mirror(node.left);

recursively mirror left subtree (which was originally right subtree)

Mirror(node.right);

recursively mirror right subtree (which was originally left subtree)

Output

Original inorder traversal:

4 2 5 1 3 6 

Inorder traversal after mirroring:

6 3 1 5 2 4 

Complexity Analysis

Time: O(n) because each node is visited once to swap children

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

vs Alternative: Iterative approaches exist but recursion is simpler and intuitive; iterative may use explicit stack with similar time and space

Edge Cases

Empty tree (root is null)

Function returns immediately without error

DSA C#

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

Tree with single node

No swaps happen, function returns after base case

DSA C#

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

Tree with only left or only right children

Children are swapped correctly, mirroring the structure

DSA C#

Node temp = node.left;
node.left = node.right;
node.right = temp;

When to Use This Pattern

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

Common Mistakes

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

Mistake: Not handling null nodes causing null reference errors
Fix: Add base case to return immediately if node is null

Summary

It flips a binary tree by swapping every left and right child recursively.

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

The key is to swap children at each node and then mirror their subtrees recursively.

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