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

Time Complexity: Mirror a Binary Tree

O(n)

Understanding Time Complexity

We want to understand how the time needed to mirror a binary tree changes as the tree grows.

How does the work increase when the tree has more nodes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function mirrorTree(node) {
  if (node === null) return null;
  const leftMirrored = mirrorTree(node.left);
  const rightMirrored = mirrorTree(node.right);
  node.left = rightMirrored;
  node.right = leftMirrored;
  return node;
}
    

This code swaps the left and right children of every node in the tree, creating a mirror image.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive call on each node to swap children.
• How many times: Once per node in the tree.

How Execution Grows With Input

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

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

Pattern observation: The operations increase linearly as the tree size grows.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Mirroring only changes the top nodes, so it takes constant time."

[OK] Correct: Every node must be visited and swapped, so the time depends on the total nodes, not just the top.

Interview Connect

Understanding this helps you explain how recursive tree algorithms scale, a key skill in many coding challenges.

Self-Check

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