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.