Mirror a Binary Tree in DSA Go - Time & Space Complexity

Time Complexity: Mirror a Binary Tree

O(n)

Understanding Time Complexity

We want to understand how long it takes to flip a binary tree so that left and right children swap places.

How does the time needed grow as the tree gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code flips the tree by swapping left and right children for every node recursively.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls visiting each node once.
• How many times: Once per node in the tree.

How Execution Grows With Input

Each node is visited once to swap its children, so the work grows directly with the number of nodes.

Input Size (n)	Approx. Operations
10	About 10 swaps
100	About 100 swaps
1000	About 1000 swaps

Pattern observation: Doubling the nodes roughly doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to mirror the tree grows linearly with the number of nodes.

Common Mistake

[X] Wrong: "The time complexity is O(log n) because the tree height is log n."

[OK] Correct: Even though the tree height is log n, every node must be visited once, so the total work depends on all nodes, not just the height.

Interview Connect

Understanding this helps you explain how recursive tree algorithms work and how their time depends on the number of nodes, a key skill in many coding interviews.

Self-Check

"What if we changed the code to only mirror the left subtree and not the right? How would the time complexity change?"