Check if Two Trees are Symmetric in DSA Javascript - Time & Space Complexity

Time Complexity: Check if Two Trees are Symmetric

O(n)

Understanding Time Complexity

We want to know how the time needed to check if two trees are mirror images grows as the trees get bigger.

How does the number of steps change when the trees have more nodes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function isMirror(t1, t2) {
  if (!t1 && !t2) return true;
  if (!t1 || !t2) return false;
  return (t1.val === t2.val) &&
         isMirror(t1.left, t2.right) &&
         isMirror(t1.right, t2.left);
}

function isSymmetric(root) {
  return isMirror(root, root);
}
    

This code checks if a tree is symmetric by comparing it to itself in a mirrored way.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls comparing pairs of nodes.
• How many times: Each node in the tree is visited once in the recursion.

How Execution Grows With Input

As the tree grows, the function checks more pairs of nodes, roughly one pair per node.

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

Pattern observation: The number of steps grows roughly in direct proportion to the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to check symmetry grows linearly with the number of nodes in the tree.

Common Mistake

[X] Wrong: "The function only checks half the nodes, so it runs in half the time."

[OK] Correct: Even though it compares pairs, every node is still visited once, so the time depends on all nodes.

Interview Connect

Understanding how recursion explores all nodes helps you explain your solution clearly and confidently in interviews.

Self-Check

"What if we changed the code to check symmetry only on one subtree instead of both? How would the time complexity change?"