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.

| | |

| | |

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

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 –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
// 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; // 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) && isSymmetric(X->right, Y->left); } // 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; // 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.

**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 🙂

## Leave a Reply

1

/

2 3

/

4

5

How is that above tree symmetric?