Check If a Binary Tree Is Symmetric

95.3k
0

Given the root of a binary tree, determine whether the tree is symmetric around its center.

A binary tree is symmetric when its left subtree is a mirror reflection of its right subtree. Therefore, nodes at mirrored positions must:

  • Both exist or both be null.

  • Contain the same value.

An empty tree and a single-node tree are both considered symmetric.

Example 1

Input: root = [1, 2, 2, 3, 4, 4, 3]

Output: true

Explanation:
The left and right subtrees are mirror images of each other. The outer nodes 3 match, the inner nodes 4 match, and the overall structure is symmetric.

Example 2

Input: root = [1, 2, 2, null, 3, null, 3]

Output: false

Explanation:
Although corresponding nodes contain the same values, their positions are not mirrored. Therefore, the tree is not symmetric.

Approach 1

Symmetry is different from checking whether the left and right subtrees are identical in the same direction.

For two nodes to be mirror images:

  • Their values must match.

  • The outer children must mirror each other:
    leftNode.left with rightNode.right.

  • The inner children must mirror each other:
    leftNode.right with rightNode.left.

This naturally forms a recursive relation because after checking one mirrored pair, the same condition must hold for the two smaller mirrored pairs below it.

Algorithm

  • If root is null, return true because an empty tree is symmetric.

  • Use a helper to compare root.left and root.right as mirrored nodes.

  • If both compared nodes are null, return true; if exactly one is null, return false because the structures differ.

  • If both nodes exist but their values differ, return false.

  • Recursively compare the outer pair leftNode.left with rightNode.right.

  • Recursively compare the inner pair leftNode.right with rightNode.left, and return true only if both comparisons succeed.

Dry Run

Symmetric Tree Approach 1 Dry Run.png

Symmetric Tree Approach 1 Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
private:
/*
* Compare two nodes that should occupy mirrored
* positions in the left and right subtrees.
*/
bool isMirror(TreeNode* leftNode, TreeNode* rightNode) {
if (leftNode == nullptr && rightNode == nullptr) {
return true;
}
/*
* If only one mirrored position contains a node,
* the structures cannot be symmetric.
*/
if (leftNode == nullptr || rightNode == nullptr) {
return false;
}
if (leftNode->val != rightNode->val) {
return false;
}
/*
* A mirror reverses directions, so outside children
* and inside children must match with each other.
*/
return isMirror(leftNode->left, rightNode->right) &&
isMirror(leftNode->right, rightNode->left);
}
public:
bool isSymmetric(TreeNode* root) {
if (root == nullptr) {
return true;
}
return isMirror(root->left, root->right);
}
};
int main() {
/*
1
/ \
2 2
/ \
3 3
*/
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(2);
root->left->left = new TreeNode(3);
root->right->right = new TreeNode(3);
Solution solution;
cout << (solution.isSymmetric(root) ? "true" : "false") << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of nodes in the binary tree. Every node is compared at most once with its mirrored counterpart.

Space Complexity: O(H), where H is the height of the binary tree, due to the recursion stack. This becomes O(N) for a skewed tree and O(log N) for a balanced tree.

Approach 2

The recursive solution keeps track of mirrored node pairs through function calls. The same information can instead be stored explicitly in a queue.

Each queue entry contains two nodes that should occupy mirrored positions.

Whenever a valid pair is processed, its children are inserted in crossed order:

  • leftNode.left with rightNode.right

  • leftNode.right with rightNode.left

As long as every stored pair matches in both structure and value, the tree remains symmetric.

Algorithm

  • If root is null, return true.

  • Push (root.left, root.right) into a queue because these nodes must mirror each other.

  • Remove one pair at a time. If both nodes are null, continue; if exactly one is null, return false.

  • If both nodes exist but their values differ, return false.

  • Push the outside pair (leftNode.left, rightNode.right) and the inside pair (leftNode.right, rightNode.left) into the queue.

  • If every pair is processed without finding a mismatch, return true.

Dry Run

Symmetric Tree Approach 2 Dry Run.png

Symmetric Tree Approach 2 Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (root == nullptr) {
return true;
}
queue<pair<TreeNode*, TreeNode*>> nodesQueue;
nodesQueue.push({root->left, root->right});
while (!nodesQueue.empty()) {
auto [leftNode, rightNode] = nodesQueue.front();
nodesQueue.pop();
if (leftNode == nullptr && rightNode == nullptr) {
continue;
}
/*
* Exactly one missing node means the mirrored
* structure is different at this position.
*/
if (leftNode == nullptr || rightNode == nullptr) {
return false;
}
if (leftNode->val != rightNode->val) {
return false;
}
/*
* Store children in crossed pairs because
* opposite directions must mirror each other.
*/
nodesQueue.push({
leftNode->left,
rightNode->right
});
nodesQueue.push({
leftNode->right,
rightNode->left
});
}
return true;
}
};
int main() {
/*
1
/ \
2 2
/ \
3 3
*/
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(2);
root->left->left = new TreeNode(3);
root->right->right = new TreeNode(3);
Solution solution;
cout << (solution.isSymmetric(root) ? "true" : "false") << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of nodes in the binary tree. Every node participates in at most one mirrored comparison.

Space Complexity: O(W), where W is the maximum width of the binary tree. The queue may store up to O(W) nodes at the same time, which can become O(N) in the worst case.

Approach 3

The recursive mirror comparison can also be reproduced using an explicit stack instead of the call stack.

Each stack entry stores a pair of nodes that should mirror one another. The same structural and value checks are performed, but valid crossed-child pairs are pushed manually.

The traversal order is depth-first, but correctness depends only on keeping the corresponding mirror positions paired together.

Algorithm

  • If root is null, return true.

  • Push (root.left, root.right) into a stack.

  • Pop one mirrored pair at a time. If both nodes are null, continue; if exactly one is null, return false.

  • If both nodes exist but their values differ, return false.

  • Push the crossed child pairs so corresponding mirror positions remain together.

  • If the stack becomes empty without any mismatch, return true.

Dry Run

Symmetric Tree Approach 3 Dry Run.png

Symmetric Tree Approach 3 Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (root == nullptr) {
return true;
}
stack<pair<TreeNode*, TreeNode*>> nodesStack;
nodesStack.push({root->left, root->right});
while (!nodesStack.empty()) {
auto [leftNode, rightNode] = nodesStack.top();
nodesStack.pop();
if (leftNode == nullptr && rightNode == nullptr) {
continue;
}
/*
* Exactly one existing node means the
* mirrored structures are different.
*/
if (leftNode == nullptr || rightNode == nullptr) {
return false;
}
if (leftNode->val != rightNode->val) {
return false;
}
/*
* Keep crossed child positions paired so
* DFS preserves the mirror comparison.
*/
nodesStack.push({
leftNode->right,
rightNode->left
});
nodesStack.push({
leftNode->left,
rightNode->right
});
}
return true;
}
};
int main() {
/*
1
/ \
2 2
/ \
3 3
*/
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(2);
root->left->left = new TreeNode(3);
root->right->right = new TreeNode(3);
Solution solution;
cout << (solution.isSymmetric(root) ? "true" : "false") << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of nodes in the binary tree. Every node is processed at most once as part of a mirrored pair.

Space Complexity: O(H), where H is the height of the binary tree, due to the explicit DFS stack. This becomes O(N) for a skewed tree and O(log N) for a balanced tree.

FAQs

Q1. Is checking symmetry the same as checking whether the left and right subtrees are identical?

No. Identical-tree comparison checks corresponding directions, such as left with left. Symmetry requires crossed comparisons: left with right and right with left.

Q2. Why are leftNode.left and rightNode.right compared together?

These nodes occupy corresponding outer positions after reflecting the tree around its center. Similarly, leftNode.right must correspond to rightNode.left.

Q3. Why must null positions also be considered?

Symmetry depends on structure as well as values. Two equal values at different structural positions do not make the tree symmetric, so missing nodes must also match their mirrored positions.

Q4. What is the main difference between the Recursive and Iterative approaches?

They perform the same mirror comparisons. Recursion stores pending comparisons in the call stack, while the iterative approaches store node pairs explicitly in a queue or stack.

Q5. Can normal level-order traversal determine whether a tree is symmetric?

Not by comparing values alone. Missing positions also affect symmetry, so BFS must either preserve null positions or directly store mirrored node pairs.

Binary TreeRecursion

Read Similar Blogs

Binary Tree

Binary Tree Paths

Given the root of a binary tree, return all paths that start at the root and end at a leaf node. Each path should be represented as a string in the form: node1-&gt;node2-&gt;node3 where the node va...

104.2k
Binary Tree

Construct a Binary Tree from Preorder and Inorder

#include using namespace std; struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int value) { val = value; left = nullptr; right = nullptr; } }; class Solution { private: int preI...

105.1k
Binary Tree

Count Nodes in a Complete Binary Tree

Input: root = [1, 2, 3, 4, 5, 6] Output: 6 Explanation: The binary tree contains a total of 6 nodes. Input: root = [1] Output: 1 Explanation: The tree contains only its root node, so the total numb...

54.2k
Comments0