Check for Symmetrical Binary Tree

Mirror Recursion

Is the Tree Symmetric?

A tree is symmetric if its left and right subtrees are mirror images. The trick: compare left→left with right→right, and left→right with right→left. The recursion crosses over.

Blue = left subtree path

Amber = right subtree path

Green = matched ✓

Red = mismatch ✗

symmetric_tree.cpp

1bool isSymmetricUtil(Node* root1, Node* root2) {2 if (root1 == NULL || root2 == NULL) {3 return root1 == root2;4 }5 return (root1->data == root2->data)6 && isSymmetricUtil(root1->left, root2->right)7 && isSymmetricUtil(root1->right, root2->left);8}

The Binary Tree (mirror axis shown as dashed line)

Step 1 / 1

Call Stack (mirrored comparisons)

in progress…

Press “Next ▶” to begin the recursion…

What's Happening Now

We start by calling isSymmetricUtil(root->left, root->right) — comparing the left subtree (2) with the right subtree (2). Press Next ▶ to step through the mirrored recursion.

Key Ideas — Why the Recursion Crosses Over

01

Mirror = cross the children

In isSameTree, you compared left with left and right with right. Here, it's root1->left with root2->right and root1->right with root2->left. The children are crossed — that's what "mirror image" means. The outer branches match each other, and the inner branches match each other.

02

Same base case as isSameTree

if (root1 == NULL || root2 == NULL) return root1 == root2 — if either is null, both must be null for symmetry. One null and one non-null means the tree has a node where its mirror doesn't — not symmetric. This is identical to the isSameTree base case.

03

Short-circuit && strikes again

The three conditions are joined by &&. If values differ, we return false immediately. If the outer mirror (left-left vs right-right) fails, we never check the inner mirror (left-right vs right-left). Watch the recursion skip the right call when the left returns false.

04

Root is never compared to itself

isSymmetric() skips the root entirely and calls isSymmetricUtil(root->left, root->right). The root is the center of the mirror — it doesn't need to match anything. Only its left and right subtrees need to be mirror images of each other.