Symmetric Tree
Symmetric Tree
Problem Description
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
A binary tree is symmetric if the left subtree is a mirror reflection of the right subtree.
Video Explanation
Approach
To determine if a binary tree is symmetric, we can use a recursive approach. We will compare the left and right subtrees of the tree.
Steps:
-
Checker Function: Create a helper function that takes two nodes as arguments and checks if they are mirrors of each other.
- If both nodes are
null, returntrue. - If one node is
nulland the other is not, returnfalse. - If the values of both nodes are different, return
false. - Recursively check the left child of the first node against the right child of the second node, and the right child of the first node against the left child of the second node.
- If both nodes are
-
Main Function: In the main function, call the checker function with the left and right children of the root.
Solutions
- C++
- Java
- Python
- JavaScript
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (!root) return true;
return isMirror(root->left, root->right);
}
bool isMirror(TreeNode* t1, TreeNode* t2) {
if (!t1 && !t2) return true;
if (!t1 || !t2) return false;
return (t1->val == t2->val) && isMirror(t1->right, t2->left) && isMirror(t1->left, t2->right);
}
};
/**
* Definition for a binary tree node.
*/
class TreeNode {
int val; // Node value
TreeNode left; // Left child
TreeNode right; // Right child
// Constructor to create a node with no children
TreeNode() {}
// Constructor to create a node with a value
TreeNode(int val) {
this.val = val;
}
// Constructor to create a node with a value and children
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
// Main function to check if the tree is symmetric
public boolean isSymmetric(TreeNode root) {
return checker(root.left, root.right); // Check if left and right subtrees are mirrors
}
// Helper function to check if two nodes are mirrors of each other
public static boolean checker(TreeNode p, TreeNode q) {
// Both nodes are null, so they are symmetric
if (p == null && q == null) {
return true;
}
// One node is null while the other is not, so they are not symmetric
if (p == null || q == null) {
return false;
}
// Values of the nodes must be the same for them to be mirrors
if (p.val != q.val) {
return false;
}
// Recursively check the left and right children for mirror symmetry
return checker(p.left, q.right) && checker(p.right, q.left);
}
}
//C++ Implementation
#include <iostream>
using namespace std;
/**
* Definition for a binary tree node.
*/
struct TreeNode {
int val; // Node value
TreeNode* left; // Pointer to left child
TreeNode* right; // Pointer to right child
// Constructor to create a node with a value
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
// Main function to check if the tree is symmetric
bool isSymmetric(TreeNode* root) {
return checker(root->left, root->right); // Check if left and right subtrees are mirrors
}
// Helper function to check if two nodes are mirrors of each other
bool checker(TreeNode* p, TreeNode* q) {
// Both nodes are null, so they are symmetric
if (!p && !q) {
return true;
}
// One node is null while the other is not, so they are not symmetric
if (!p || !q) {
return false;
}
// Values of the nodes must be the same for them to be mirrors
if (p->val != q->val) {
return false;
}
// Recursively check the left and right children for mirror symmetry
return checker(p->left, q->right) && checker(p->right, q->left);
}
};
//Python Implementation
class TreeNode:
def __init__(self, x):
self.val = x # Node value
self.left = None # Left child
self.right = None # Right child
class Solution:
# Main function to check if the tree is symmetric
def isSymmetric(self, root: TreeNode) -> bool:
return self.checker(root.left, root.right) # Check if left and right subtrees are mirrors
# Helper function to check if two nodes are mirrors of each other
def checker(self, p: TreeNode, q: TreeNode) -> bool:
# Both nodes are null, so they are symmetric
if not p and not q:
return True
# One node is null while the other is not, so they are not symmetric
if not p or not q:
return False
# Values of the nodes must be the same for them to be mirrors
if p.val != q.val:
return False
# Recursively check the left and right children for mirror symmetry
return self.checker(p.left, q.right) and self.checker(p.right, q.left)
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
def isMirror(t1, t2):
if not t1 and not t2:
return True
if not t1 or not t2:
return False
return (t1.val == t2.val) and isMirror(t1.right, t2.left) and isMirror(t1.left, t2.right)
return isMirror(root.left, root.right) if root else True
var isSymmetric = function(root) {
if (!root) return true;
function isMirror(t1, t2) {
if (!t1 && !t2) return true;
if (!t1 || !t2) return false;
return (t1.val === t2.val) && isMirror(t1.right, t2.left) && isMirror(t1.left, t2.right);
}
return isMirror(root.left, root.right);
};
Done with this topic? Mark it as complete to track your progress.
Related Practice Problems
Handpicked problems sharing similar algorithmic topic tags
Cousins in Binary Tree
This document includes the solution to the problem of determining if two nodes in a binary tree are cousins, along with the approach and implementation.
Diameter of Binary Tree
Solving the Diameter of Binary Tree problem using a Recursive Depth-First Search (DFS) approach.
Maximum Depth of Binary Tree
Solving the Maximum Depth of Binary Tree problem using a Recursive Depth-First Search (DFS) approach.
💬 Discuss this page
Have a question or spot something confusing in "Symmetric Tree"? Ask below — it's backed by GitHub Discussions, so maintainers get notified like any other GitHub activity.