Check if a Binary Tree is Symmetric or not

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.

For example, below are some binary trees that have symmetric structure.

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

1. both trees are empty or both are non-empty and
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 –

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.

Alternate approach:

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.

(1 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Subscribe
Notify of
Guest

1
/
2 3
/
4

5

How is that above tree symmetric?

Guest

Hi in the recursive approach the function wont give correct results though the idea is correct . Here caller and called function both have same name also . in the called function we should add an check to validate symmetric data as well in both sub trees . something like below :