Mirror a Binary Tree in DSA Go

Mental Model

Flip the tree so left and right children swap places at every node.

Analogy: Imagine holding a tree-shaped mirror and seeing the tree's reflection flipped left to right.

    1
   / \
  2   3
 /     \
4       5

Dry Run Walkthrough

Input: tree: 1 with left child 2 (which has left child 4) and right child 3 (which has right child 5)

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

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

    1
   / \
  3   2
 /     \
5       4

Why: Swapping children at root flips the top level branches

Step 2: move to left child 3, swap its left and right children (left is null, right is 5)

    1
   / \
  3   2
 /     \
5       4

Why: Swapping children of node 3 moves 5 to left side

Step 3: move to right child 2, swap its left and right children (left is 4, right is null)

    1
   / \
  3   2
 /     \
5       4

Why: Swapping children of node 2 moves 4 to right side

Step 4: move to node 5 (left child of 3), no children to swap

    1
   / \
  3   2
 /     \
5       4

Why: Leaf nodes have no children to swap

Step 5: move to node 4 (right child of 2), no children to swap

    1
   / \
  3   2
 /     \
5       4

Why: Leaf nodes have no children to swap

Result:

    1
   / \
  3   2
 /     \
5       4

Annotated Code

DSA Go

package main

import "fmt"

// TreeNode defines a node in a binary tree
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// mirrorTree swaps left and right children recursively to mirror the tree
func mirrorTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    // swap left and right children
    root.Left, root.Right = root.Right, root.Left
    // recursively mirror left subtree
    mirrorTree(root.Left)
    // recursively mirror right subtree
    mirrorTree(root.Right)
    return root
}

// printTree prints the tree in preorder with structure
func printTree(root *TreeNode) {
    if root == nil {
        return
    }
    fmt.Print(root.Val, " ")
    printTree(root.Left)
    printTree(root.Right)
}

func main() {
    // build tree: 1
    //           /   \
    //          2     3
    //         /       \
    //        4         5
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 3}
    root.Left.Left = &TreeNode{Val: 4}
    root.Right.Right = &TreeNode{Val: 5}

    fmt.Print("Original tree preorder: ")
    printTree(root)
    fmt.Println()

    mirrorTree(root)

    fmt.Print("Mirrored tree preorder: ")
    printTree(root)
    fmt.Println()
}

if root == nil { return nil }

stop recursion at leaf's child

root.Left, root.Right = root.Right, root.Left

swap left and right children at current node

mirrorTree(root.Left)

recursively mirror left subtree after swap

mirrorTree(root.Right)

recursively mirror right subtree after swap

Output

Original tree preorder: 1 2 4 3 5 

Mirrored tree preorder: 1 3 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 uses call stack; iterative may use explicit stack with similar time and space

Edge Cases

empty tree (root is nil)

function returns nil immediately without error

DSA Go

if root == nil { return nil }

single node tree

no swaps needed, returns the same node

DSA Go

if root == nil { return nil }

tree with only left or only right children

children are swapped correctly, mirroring the structure

DSA Go

root.Left, root.Right = root.Right, root.Left

When to Use This Pattern

When asked to flip or invert a binary tree structure, use the mirror pattern by swapping children recursively to get the reflected tree.

Common Mistakes

Mistake: Swapping children but not recursively calling mirror on subtrees
Fix: After swapping, recursively call mirrorTree on both left and right children

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

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 structure.

The key is to swap children first, then recursively mirror subtrees.

Practice

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

easy

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

B. Remove all leaf nodes from 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 A

4. Quick Check:

   Mirror = Swap children [OK]

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

Common Mistakes:

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

2. Which Go function signature correctly represents a function to mirror a binary tree node?

easy

A. func mirrorTree(root *TreeNode) int

B. func mirrorTree(root TreeNode) TreeNode

C. func mirrorTree(root TreeNode) bool

D. func mirrorTree(root *TreeNode) *TreeNode

Solution

1. Step 1: Understand pointer usage in Go trees

   Binary trees are usually represented with pointers to nodes to allow modification.

2. Step 2: Check return type for mirrored tree

   The function should return a pointer to the root of the mirrored tree.

3. Final Answer:

   func mirrorTree(root *TreeNode) *TreeNode -> Option D

4. Quick Check:

   Pointer input and output for tree nodes [OK]

Hint: Use pointers for tree nodes to modify and return [OK]

Common Mistakes:

• Passing tree nodes by value instead of pointer
• Returning wrong type like int or bool
• Not returning the mirrored tree root

3. What is the output of the following Go code that mirrors a binary tree?

type TreeNode struct {
    Val int
    Left, Right *TreeNode
}

func mirrorTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    left := mirrorTree(root.Left)
    right := mirrorTree(root.Right)
    root.Left, root.Right = right, left
    return root
}

func main() {
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 3}
    mirrorTree(root)
    fmt.Println(root.Val, root.Left.Val, root.Right.Val)
}

medium

A. 2 1 3

B. 1 2 3

C. 1 3 2

D. 3 1 2

Solution

1. Step 1: Understand the initial tree structure

   Root is 1, left child is 2, right child is 3.

2. Step 2: Apply mirrorTree function

   Mirror swaps left and right children at root, so left becomes 3 and right becomes 2.

3. Final Answer:

   1 3 2 -> Option C

4. Quick Check:

   Swapped children values = 1 3 2 [OK]

Hint: Mirror swaps left and right children recursively [OK]

Common Mistakes:

• Not swapping children correctly
• Printing values before mirroring
• Confusing left and right child values

4. Identify the error in this Go function that attempts to mirror a binary tree:

func mirrorTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    mirrorTree(root.Left)
    mirrorTree(root.Right)
    root.Left, root.Right = root.Right, root.Left
    return root
}

medium

A. The base case is missing

B. The recursive calls do not assign the mirrored subtrees back to root.Left and root.Right

C. The function returns the wrong type

D. Swapping children should happen before recursive calls

Solution

1. Step 1: Analyze recursive calls

   The function calls mirrorTree on root.Left and root.Right but ignores their returned mirrored subtrees.

2. Step 2: Check assignment of mirrored subtrees

   Without assigning returned values, the subtrees are not updated, so mirror is incomplete.

3. Final Answer:

   The recursive calls do not assign the mirrored subtrees back to root.Left and root.Right -> Option B

4. Quick Check:

   Assign returned mirrored subtrees to children [OK]

Hint: Always assign recursive results back to node children [OK]

Common Mistakes:

• Ignoring returned subtree pointers
• Swapping children before recursion
• Missing base case (though present here)

5. Given a binary tree, how would you modify the mirror function to also count how many nodes were swapped during the mirroring process?

hard

A. Add a counter variable and increment it each time left and right children are swapped recursively

B. Return the sum of node values instead of mirroring

C. Only swap nodes if their values are even

D. Use a queue to traverse the tree without recursion

Solution

1. Step 1: Understand the goal

   We want to count how many nodes had their children swapped during mirroring.

2. Step 2: Modify mirror function to count swaps

   Each time we swap left and right children at a node, increment a counter and add counts from recursive calls.

3. Final Answer:

   Add a counter variable and increment it each time left and right children are swapped recursively -> Option A

4. Quick Check:

   Count swaps during recursion [OK]

Hint: Count swaps inside recursion when swapping children [OK]

Common Mistakes:

• Counting node values instead of swaps
• Not accumulating counts from recursive calls
• Using traversal without swapping