Mirror a Binary Tree in DSA Go - Deep Dive

Overview - Mirror a Binary Tree

What is it?

Mirroring a binary tree means swapping the left and right children of every node in the tree. This creates a new tree that looks like the original tree flipped around its center. It is like looking at the tree in a mirror. This operation changes the structure but keeps all the nodes and their values.

Why it matters

Mirroring a binary tree helps us understand tree structures better and is useful in problems involving symmetry or tree transformations. Without this concept, we would struggle to manipulate tree shapes or solve problems that require reversing tree layouts. It also helps in algorithms that need to compare or transform trees efficiently.

Where it fits

Before learning to mirror a binary tree, you should understand what a binary tree is and how to traverse it. After mastering mirroring, you can explore tree algorithms like tree rotations, balancing, and more complex transformations such as tree isomorphism or serialization.

Mental Model

Core Idea

Mirroring a binary tree means swapping every node's left and right children to create a flipped version of the original tree.

Think of it like...

Imagine holding a family photo and flipping it horizontally so that everyone's left and right sides are swapped, but the people and their positions 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 stores a value and pointers to its children or null if none exist. For example, a node with value 1 might have left child 2 and right child 3.

Result

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

Understanding the basic structure of binary trees is essential before changing or manipulating them.

2

Foundation

Traversing a Binary Tree

Concept: Learn how to visit each node in a binary tree systematically.

Traversal means visiting nodes in a specific order. Common ways are preorder (node, left, right), inorder (left, node, right), and postorder (left, right, node). Traversal helps us access or modify nodes one by one.

Result

You can visit all nodes in a tree and perform actions like printing or modifying values.

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

3

Intermediate

Swapping Children to Mirror Nodes

🤔Before reading on: do you think mirroring a tree means swapping only the root's children or all nodes' children? Commit to your answer.

Concept: Mirroring requires swapping the left and right children of every node, not just the root.

To mirror a tree, start at the root. Swap its left and right children. Then do the same for each child node recursively until all nodes have swapped children.

Result

The tree becomes a mirror image with left and right children flipped at every node.

Knowing that every node's children must be swapped prevents incomplete mirroring and ensures the entire tree is flipped.

4

Intermediate

Recursive Approach to Mirror Tree

🤔Before reading on: do you think recursion or iteration is simpler for mirroring a tree? Commit to your answer.

Concept: Use recursion to mirror the tree by swapping children and calling the same process on each child.

In Go, define a function that takes a node. If the node is nil, return. Otherwise, swap its left and right children. Then call the function recursively on the new left and right children.

Result

The entire tree is mirrored by visiting all nodes through recursive calls.

Recursion naturally fits tree structures and simplifies the mirroring logic by handling subtrees the same way.

5

Advanced

Iterative Mirroring Using a Queue

🤔Before reading on: do you think iterative mirroring is more complex or simpler than recursion? Commit to your answer.

Concept: Use a queue to visit nodes level by level and swap their children iteratively.

Initialize a queue with the root node. While the queue is not empty, dequeue a node, swap its children, and enqueue the children if they exist. Repeat until all nodes are processed.

Result

The tree is mirrored without recursion, useful when recursion depth is a concern.

Understanding iterative mirroring helps handle large trees where recursion might cause stack overflow.

6

Expert

Mirroring Impact on Tree Properties

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

Concept: Mirroring changes the tree structure and can affect properties like ordering in binary search trees.

Mirroring swaps children, so a binary search tree (BST) loses its ordering property after mirroring. The mirrored tree is no longer a BST but still a valid binary tree. This matters when mirroring is used in algorithms relying on BST properties.

Result

Mirroring can break BST properties, so it must be used carefully depending on the tree type.

Knowing how mirroring affects tree properties prevents bugs in algorithms that assume specific tree structures.

Under the Hood

Mirroring works by recursively or iteratively swapping pointers to left and right children at each node. The process traverses the entire tree, touching every node exactly once. Memory-wise, no new nodes are created; only references are changed. In recursion, the call stack grows with tree height, while iteration uses an explicit queue or stack.

Why designed this way?

The design leverages the natural recursive structure of trees, making the algorithm simple and elegant. Alternatives like iterative methods exist but are more complex. Swapping pointers in place avoids extra memory use, making it efficient.

Start
  │
  ▼
[Node]
  │ Swap left and right children
  ▼
[Left Child] ← Recursive call
  │
  ▼
[Right Child] ← Recursive call
  │
  ▼
End

Myth Busters - 3 Common Misconceptions

Quick: Does mirroring a binary tree create new nodes or just rearrange existing ones? Commit yes or no.

Common Belief: Mirroring creates a new tree with new nodes that copy the original values.

Reality: Mirroring only swaps the existing nodes' left and right pointers; no new nodes are created.

Why it matters: Thinking new nodes are created leads to unnecessary memory use and confusion about the operation's cost.

Quick: After mirroring, does a binary search tree remain a valid BST? Commit yes or no.

Common Belief: Mirroring keeps the binary search tree property intact.

Reality: Mirroring breaks the BST property because left and right children are swapped, reversing the order.

Why it matters: Assuming BST property remains can cause incorrect search results or algorithm failures.

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

Common Belief: Swapping only the root's children mirrors the entire tree.

Reality: All nodes' children must be swapped recursively or iteratively to mirror the whole tree.

Why it matters: Partial swapping leads to incomplete mirroring and incorrect tree structure.

Expert Zone

1

Mirroring a tree in place is efficient but changes the original tree, so cloning may be needed if preservation is required.

2

Recursive mirroring depth depends on tree height; for very deep trees, iterative methods prevent stack overflow.

3

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

When NOT to use

Avoid mirroring when the tree's ordering or balance properties must be preserved, such as in binary search trees or AVL trees. Instead, use tree rotations or rebuild the tree to maintain properties.

Production Patterns

Mirroring is used in graphics for scene graphs, inverting decision trees for testing, and in algorithms that require symmetric tree comparisons or transformations.

Connections

Tree Traversal

Mirroring builds on tree traversal by visiting every node to swap children.

Understanding traversal methods is essential to implement mirroring correctly and efficiently.

Binary Search Trees

Mirroring affects BST properties by reversing child positions.

Knowing how mirroring changes BSTs helps avoid logical errors in search or insert operations after mirroring.

Image Reflection in Computer Graphics

Mirroring a binary tree is conceptually similar to reflecting an image across an axis.

Recognizing this connection helps understand symmetry operations across different fields like graphics and data structures.

Common Pitfalls

#1 Swapping children only at the root node.

Wrong approach:

func mirror(node *Node) {
if node == nil {
return
}
node.Left, node.Right = node.Right, node.Left
// No recursive calls
}

Correct approach:

func mirror(node *Node) {
if node == nil {
return
}
node.Left, node.Right = node.Right, node.Left
mirror(node.Left)
mirror(node.Right)
}

Root cause:

Misunderstanding that mirroring requires swapping children at every node, not just the root.

#2 Assuming mirrored binary search tree remains valid for search operations.

Wrong approach:

// After mirroring a BST, perform normal BST search
func search(node *Node, val int) bool {
if node == nil {
return false
}
if val == node.Val {
return true
} else if val < node.Val {
return search(node.Left, val)
} else {
return search(node.Right, val)
}
}

Correct approach:

// Recognize BST property is lost after mirroring; use tree traversal or rebuild BST
// No direct search on mirrored tree as BST

Root cause:

Not realizing that mirroring swaps children and breaks BST ordering.

#3 Using recursion without base case leading to stack overflow on empty nodes.

Wrong approach:

func mirror(node *Node) {
node.Left, node.Right = node.Right, node.Left
mirror(node.Left)
mirror(node.Right)
}

Correct approach:

func mirror(node *Node) {
if node == nil {
return
}
node.Left, node.Right = node.Right, node.Left
mirror(node.Left)
mirror(node.Right)
}

Root cause:

Forgetting to check for nil nodes before recursion causes runtime errors.

Key Takeaways

Mirroring a binary tree means swapping the left and right children of every node to create a flipped version of the tree.

This operation changes the tree structure but does not create new nodes or change node values.

Recursion is a natural and simple way to implement mirroring by applying the same swap process to all nodes.

Mirroring breaks properties like binary search tree ordering, so it must be used carefully depending on the tree type.

Understanding traversal and tree structure is essential to correctly mirror a tree and avoid common mistakes.

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