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

Time Complexity: Check if Two Trees are Symmetric

O(n)

Understanding Time Complexity

We want to understand 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.

bool isMirror(TreeNode* t1, TreeNode* 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);
}

bool isSymmetric(TreeNode* root) {
    return isMirror(root, root);
}
    

This code checks if a tree is symmetric by comparing its left and right sides recursively.

Identify Repeating Operations

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

How Execution Grows With Input

Each node is checked once against its mirror node, so the steps grow as the number of nodes grows.

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

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 visited once, so the time still 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 code to check symmetry iteratively using a queue? How would the time complexity change?"