Mirror a Binary Tree in DSA C++ - 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 number of steps grow when the tree has more nodes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void mirrorTree(Node* root) {
    if (root == nullptr) return;
    mirrorTree(root->left);
    mirrorTree(root->right);
    std::swap(root->left, root->right);
}
    

This code swaps the left and right children of every node in the tree, effectively mirroring it.

Identify Repeating Operations

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

How Execution Grows With Input

Each node is visited once, so the total steps grow 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 work grows in a straight line with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Mirroring only swaps the root's children, so it takes constant time."

[OK] Correct: Every node's children must be swapped, so the whole tree must be visited, not just the root.

Interview Connect

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

Self-Check

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