Check if Two Trees are Symmetric in DSA Go - 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.

func isSymmetric(t1, t2 *TreeNode) bool {
    if t1 == nil && t2 == nil {
        return true
    }
    if t1 == nil || t2 == nil {
        return false
    }
    return t1.Val == t2.Val && isSymmetric(t1.Left, t2.Right) && isSymmetric(t1.Right, t2.Left)
}

This code checks if two trees are mirror images by comparing nodes and their opposite children 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 tree.

How Execution Grows With Input

Each node pair is checked once, so the steps grow directly with the number of nodes.

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

Pattern observation: The work grows in a straight line as the tree size grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to check symmetry grows directly 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 nodes in 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 only one subtree against itself instead of two? How would the time complexity change?"