Check if given 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.


          |               |                  |
          |               |                  |
          1               1                  1
        / | \           / | \              / | \
       /  |  \         /  |  \            /  |  \
      2   |   3       2   |   3          2   |   3
       \  |  /       / \  |  / \        /    |    \
        5 | 6       4   5 | 6   7      4     |     7 
          |               |                  |
          |               |                  |

 


 

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 –
 

Download   Run Complete Code

 
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.
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Sort by:   newest | oldest | most voted
Kerr
Kerr
1 / 2 3 / 4 5 How is that above tree symmetric?
wpDiscuz