Check if Two Trees are Symmetric in DSA Typescript - 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 work increase when the trees have more nodes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function isSymmetric(t1: TreeNode | null, t2: TreeNode | null): boolean {
  if (!t1 && !t2) return true;
  if (!t1 || !t2) return false;
  return (t1.val === t2.val) &&
         isSymmetric(t1.left, t2.right) &&
         isSymmetric(t1.right, t2.left);
}
    

This function checks if two trees are mirror images by comparing nodes recursively.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls comparing pairs of nodes.
• How many times: Once for each node in the trees, visiting all nodes.

How Execution Grows With Input

As the number of nodes grows, the function checks each node pair once.

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

Pattern observation: The work grows directly with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to check symmetry grows in a straight line with the number of nodes.

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, it still visits every node once, so the time grows with all nodes.

Interview Connect

Understanding how recursive tree checks scale helps you explain your approach clearly and confidently in interviews.

Self-Check

"What if we changed the function to check symmetry iteratively using a queue? How would the time complexity change?"