Given a binary tree, write an efficient algorithm to check if it is symmetric binary tree or not. i.e. left subtree and right subtree are mirror images or each other.
The idea is very simple. The tree has symmetric structure if left subtree and right subtree are mirror images of each other. Two trees are mirror images of each other if
2. left subtree is mirror image of right subtree and
3. right subtree is mirror image of left subtree
We can easily check this using recursion. Following is the implementation of the idea –
C++ implementation –
// Function to check if subtree rooted at X and Y are mirror images
// of each other or not
bool isSymmetric(Node *X, Node *Y)
// base case: if both tree are empty
if (X == nullptr && Y == nullptr)
// return true if
// 1. both trees are non-empty and
// 2. left subtree is mirror image of right subtree and
// 3. right subtree is mirror image of left subtree
return (X != nullptr && Y != nullptr) &&
isSymmetric(X->left, Y->right) &&
// Function to check if given binary Tree has a symmetric structure or not
bool isSymmetric(Node *root)
// base case: if tree is empty
if (root == nullptr)
// return true if left subtree and right subtree are
// mirror images or each other
return isSymmetric(root->left, root->right);
The time complexity of above solution is O(n) and need O(h) extra space for the call stack where h is the height of the tree.
We can also check for symmetric structure by converting either left subtree or the right subtree to their mirror image and then check if both left and right subtree have identical structure or not. The time complexity of this approach remains O(n) but it modifies the tree structure. We can restore the tree back to its original structure by again taking mirror of corresponding left or right subtree.
Exercise: Extend the solution to check for symmetric content along with symmetric structure.
Thanks for reading.