Mirror a Binary Tree in DSA Typescript - 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.

function mirrorTree(root: TreeNode | null): TreeNode | null {
  if (root === null) return null;
  const left = mirrorTree(root.left);
  const 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: The time grows linearly as the tree size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to mirror the tree grows in direct proportion to the number of nodes.

Common Mistake

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

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

Interview Connect

Understanding this helps you explain how recursive tree algorithms work and how their time depends on node count, a key skill in many coding challenges.

Self-Check

"What if we changed the tree to a linked list (all nodes have only one child)? How would the time complexity change?"