Check if a given binary tree is symmetric tree or not
Write a program to check if the given binary tree is symmetric tree or not. A symmetric tree is defined as a tree which is mirror image of itself about the root node. For example, following tree is a symmetric tree.
whereas, following tree is not a symmetric tree.
Video coming soon!
Subscribe for more updates
Preparing for interviews? IDeserve team is here to help.
Create your profile
Create your profile, and here is what you will get:
1: Interview practice platform.
2: Once you are ready to take the interview, IDeserve team will help you get connected to the best job opportunities.
3: Personalized mentorship from IDeserve team once your interview process has started.
Creation of profile shouldn't take more than 2 minutes.
The algorithm is an implementation of a simple idea that - 1. For given two trees, if both trees are empty then they are mirror images of one another. Else they have to satisfy following conditions: 2. Root values of both trees have to be same. 3. Left sub-tree of tree1 should be mirror image of right sub-tree of tree2. 4. Right sub-tree of tree1 should be mirror image of left sub-tree of tree2.
Initial call to isSymmetric(TreeNode root1, TreeNode root2) is made with root1 = root and root2 = root.
Time complexity of this algorithm is O(n) since in the worst case each node need to be visited once.
Support us by whitelisting IDeserve in your ad-blocker.