Log inSign up
easyleetcodeNot Started

Symmetric Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1 · Example 1: Symmetric Tree:

Input: root = [1, 2, 2, 3, 4, 4, 3]
Output: true
Explanation: Outer nodes 3 == 3, inner nodes 4 == 4. Tree is a mirror image.

Example 2 · Example 2: Asymmetric Tree:

Input: root = [1, 2, 2, null, 3, null, 3]
Output: false
Explanation: Right child of left node is 3, but right child of right node is 3 (not a mirror).

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • -100 <= Node.val <= 100

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the cross-child mirror recursion pattern.
  • Implement iterative mirror queue pairing.
  • Understand why naive inorder palindromic check fails without null markers.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Check mirror symmetry of binary tree around root.
  • Cross-child comparison (outer with outer, inner with inner).

Algorithmic Decision Tree:

  • return isMirror(root.left, root.right);
  • isMirror(t1, t2): if (!t1 && !t2) return true;
  • if (!t1 || !t2 || t1.val != t2.val) return false;
  • return isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);

Connected Patterns:

Same TreeInvert Binary TreeBinary Tree Level Order Traversal

1. Level Order Palindrome Verification

Intuition

Traverse tree using BFS level by level. In each level, record values of all nodes (using null for missing nodes). Check if each level array is a palindrome.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: If root == null return true.
  2. Step 2: Run BFS storing node values per level including nulls.
  3. Step 3: If any level is not palindromic, return false.
  4. Step 4: Return true.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 bool isSymmetric(TreeNode* root) {
10 if (!root) return true;
11 queue<TreeNode*> q;
12 q.push(root->left);
13 q.push(root->right);
14 while (!q.empty()) {
15 int sz = q.size();
16 vector<int> vals;
17 for (int i = 0; i < sz; i += 2) {
18 TreeNode* t1 = q.front(); q.pop();
19 TreeNode* t2 = q.front(); q.pop();
20 if (!t1 && !t2) continue;
21 if (!t1 || !t2 || t1->val != t2->val) return false;
22 q.push(t1->left); q.push(t2->right);
23 q.push(t1->right); q.push(t2->left);
24 }
25 }
26 return true;
27 }
28};
29
30int main() {
31 // Sample driver execution
32 cout << "Execution completed successfully." << endl;
33 return 0;
34}
35

Time & Space Complexity

  • Time complexity: O(n) — Processes all nodes and checks level arrays.
  • Space complexity: O(w) — Queue holds level width.

2. Iterative Stack Mirror Verification

Intuition

Push root.left and root.right onto stack. While stack is not empty: pop t2 and t1. Check equality. Push cross pairs: (t1.left, t2.right) and (t1.right, t2.left).

When to apply: When avoiding recursive call stacks.

Algorithm

  1. Step 1: If root == null return true.
  2. Step 2: Stack s; push root.left, root.right.
  3. Step 3: While s not empty: pop t2, t1.
  4. - If !t1 && !t2 continue.
  5. - If !t1 || !t2 || t1.val != t2.val return false.
  6. - Push cross pairs.
  7. Step 4: Return true.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 bool isSymmetric(TreeNode* root) {
10 if (!root) return true;
11 stack<TreeNode*> st;
12 st.push(root->left);
13 st.push(root->right);
14 while (!st.empty()) {
15 TreeNode* t2 = st.top(); st.pop();
16 TreeNode* t1 = st.top(); st.pop();
17 if (!t1 && !t2) continue;
18 if (!t1 || !t2 || t1->val != t2->val) return false;
19 st.push(t1->left);
20 st.push(t2->right);
21 st.push(t1->right);
22 st.push(t2->left);
23 }
24 return true;
25 }
26};
27
28int main() {
29 // Sample driver execution
30 cout << "Execution completed successfully." << endl;
31 return 0;
32}
33

Time & Space Complexity

  • Time complexity: O(n) — Visits all nodes in O(n) time.
  • Space complexity: O(h) — Stack holds at most O(h) nodes.

3. Recursive Mirror DFS

Intuition

Define isMirror(t1, t2). If both null, return true. If one null or values differ, return false. Return isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left).

When to apply: Standard optimal solution.

Algorithm

  1. Step 1: If root == null return true.
  2. Step 2: Return isMirror(root.left, root.right).
  3. Step 3: In isMirror(t1, t2):
  4. - If !t1 && !t2 return true.
  5. - If !t1 || !t2 || t1.val != t2.val return false.
  6. - Return isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left).

Symmetric Tree Trace for root = [1, 2, 2, 3, 4, 4, 3]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Compare root
Visual state
Values and pointers at this exact step
tree
Root
1
L Child
2
R Child
2

Node order shown; add connections to display explicit tree edges.

t1: 2at2: 2b
Check / comparison
left.val (2) == right.val (2)
Decision / next transition
Match. Compare outer pair (3, 3) and inner pair (4, 4).
Why this step matters

Step 1: Compare root.left (2) and root.right (2). Both values equal 2. Match!

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 bool isMirror(TreeNode* t1, TreeNode* t2) {
10 if (!t1 && !t2) return true;
11 if (!t1 || !t2 || t1->val != t2->val) return false;
12 return isMirror(t1->left, t2->right) && isMirror(t1->right, t2->left);
13 }
14 bool isSymmetric(TreeNode* root) {
15 if (!root) return true;
16 return isMirror(root->left, root->right);
17 }
18};
19
20int main() {
21 // Sample driver execution
22 cout << "Execution completed successfully." << endl;
23 return 0;
24}
25

Time & Space Complexity

  • Time complexity: O(n) — Visits all nodes in O(n) time with early exit on mismatch.
  • Space complexity: O(h) — Call stack depth is tree height O(h).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Level Palindrome BFSO(n)O(w)Queue checks each row for palindromic symmetry.Level array checks.
2.Iterative StackO(n)O(h)Stack paired cross comparisons.Explicit stack.
3.Recursive Mirror DFSOptimalO(n)O(h)Cross-child mirror recursion.None. This is optimal.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Single node tree: root = [1] -> returns true.
  • Two-node tree: root = [1, 2] -> returns false.
  • Asymmetric values with symmetric shape.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain why simple Inorder palindrome check can fail on trees like [1, 2, 2, 2, null, 2] unless null nodes are explicitly tracked.
  2. Clearly describe the cross-checking logic: outer nodes (t1.left, t2.right) and inner nodes (t1.right, t2.left).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.When checking mirror symmetry between two subtrees t1 and t2, which children must be compared together?

Back to DSA Sheet