Given a binary tree, check whether it is a mirror of itself.
Examples:
Input:
5
/ \
3 3
/ \ / \
8 9 9 8
Output: Symmetric
Input:
5
/ \
8 7
\ \
4 3
Output: Not Symmetric
Approach: The idea is to traverse the tree using Morris Traversal and Reverse Morris Traversal to traverse the given binary tree and at each step check that the data of the current node is equal in both the traversals. If at any step the data of the nodes are different. Then, the given tree is not Symmetric Binary Tree.
Below is the implementation of the above approach:
C++
// C++ implementation to check// if Tree is symmetric or not#include <bits/stdc++.h>using namespace std;// A Binary Tree Nodestruct Node { int data; Node* left; Node* right; Node(int val) { data = val; left = right = NULL; }};// Function to check if the given// binary tree is Symmetric or notbool isSymmetric(struct Node* root){ Node *curr1 = root, *curr2 = root; // Loop to traverse the tree in // Morris Traversal and // Reverse Morris Traversal while (curr1 != NULL && curr2 != NULL) { if (curr1->left == NULL && curr2->right == NULL) { if (curr1->data != curr2->data) return false; curr1 = curr1->right; curr2 = curr2->left; } else if (curr1->left != NULL && curr2->right != NULL) { Node* pre1 = curr1->left; Node* pre2 = curr2->right; while (pre1->right != NULL && pre1->right != curr1 && pre2->left != NULL && pre2->left != curr2) { pre1 = pre1->right; pre2 = pre2->left; } if (pre1->right == NULL && pre2->left == NULL) { // Here, we are threading the Node pre1->right = curr1; pre2->left = curr2; curr1 = curr1->left; curr2 = curr2->right; } else if (pre1->right == curr1 && pre2->left == curr2) { // Unthreading the nodes pre1->right = NULL; pre2->left = NULL; if (curr1->data != curr2->data) return false; curr1 = curr1->right; curr2 = curr2->left; } else return false; } else return false; } if (curr1 != curr2) return false; return true;}// Driver Codeint main(){ /* 5 / \ 3 3 / \ / \ 8 9 9 8 */ // Creation of Binary tree Node* root = new Node(5); root->left = new Node(3); root->right = new Node(3); root->left->left = new Node(8); root->left->right = new Node(9); root->right->left = new Node(9); root->right->right = new Node(8); if (isSymmetric(root)) cout << "Symmetric"; else cout << "Not Symmetric"; return 0;} |
Java
// Java implementation to check// if Tree is symmetric or notclass GFG{// A Binary Tree Nodestatic class Node{ int data; Node left; Node right; Node(int val) { data = val; left = right = null; }};// Function to check if the given// binary tree is Symmetric or notstatic boolean isSymmetric(Node root){ Node curr1 = root, curr2 = root; // Loop to traverse the tree in // Morris Traversal and // Reverse Morris Traversal while (curr1 != null && curr2 != null) { if (curr1.left == null && curr2.right == null) { if (curr1.data != curr2.data) return false; curr1 = curr1.right; curr2 = curr2.left; } else if (curr1.left != null && curr2.right != null) { Node pre1 = curr1.left; Node pre2 = curr2.right; while (pre1.right != null && pre1.right != curr1 && pre2.left != null && pre2.left != curr2) { pre1 = pre1.right; pre2 = pre2.left; } if (pre1.right == null && pre2.left == null) { // Here, we are threading the Node pre1.right = curr1; pre2.left = curr2; curr1 = curr1.left; curr2 = curr2.right; } else if (pre1.right == curr1 && pre2.left == curr2) { // Unthreading the nodes pre1.right = null; pre2.left = null; if (curr1.data != curr2.data) return false; curr1 = curr1.right; curr2 = curr2.left; } else return false; } else return false; } if (curr1 != curr2) return false; return true;}// Driver Codepublic static void main(String[] args){ /* 5 / \ 3 3 / \ / \ 8 9 9 8 */ // Creation of Binary tree Node root = new Node(5); root.left = new Node(3); root.right = new Node(3); root.left.left = new Node(8); root.left.right = new Node(9); root.right.left = new Node(9); root.right.right = new Node(8); if (isSymmetric(root)) System.out.print("Symmetric"); else System.out.print("Not Symmetric");}}// This code is contributed by Rajput-Ji |
Python3
# Python3 implementation to check # if Tree is symmetric or not# A Binary Tree Node class Node: def __init__(self, val): self.data = val self.left = self.right = None # Function to check if the given # binary tree is Symmetric or notdef isSymmetric(root): curr1 = root curr2 = root # Loop to traverse the tree in # Morris Traversal and # Reverse Morris Traversal while curr1 != None and curr2 != None: if (curr1.left == None and curr2.right == None): if curr1.data != curr2.data: return False curr1 = curr1.right curr2 = curr2.left elif curr1 != None and curr2 != None: pre1 = curr1.left pre2 = curr2.right while (pre1.right != None and pre1.right != curr1 and pre2.left != None and pre2.left != curr2): pre1 = pre1.right pre2 = pre2.left if pre1.right == None and pre2.left == None: # Here, we are threading the Node pre1.right = curr1 pre2.left = curr2 curr1 = curr1.left curr2 = curr2.right elif (pre1.right == curr1 and pre2.left == curr2): # Unthreading the nodes pre1.right = None pre2.left = None if curr1.data != curr2.data: return False curr1 = curr1.right curr2 = curr2.left else: return False else: return False if curr1 != curr2: return False return True# Driver codedef main(): # # 5 # / \ # 3 3 # / \ / \ #8 9 9 8 # Creation of Binary tree root = Node(5) root.left = Node(3) root.right = Node(3) root.left.left = Node(8) root.left.right = Node(9) root.right.left = Node(9) root.right.right = Node(8) if isSymmetric(root): print("Symmetric") else: print("Not Symmetric")main()# This code is contributed by Stuti Pathak |
C#
// C# implementation to check// if Tree is symmetric or notusing System;class GFG{// A Binary Tree Nodeclass Node{ public int data; public Node left; public Node right; public Node(int val) { data = val; left = right = null; }};// Function to check if the given// binary tree is Symmetric or notstatic bool isSymmetric(Node root){ Node curr1 = root, curr2 = root; // Loop to traverse the tree in // Morris Traversal and // Reverse Morris Traversal while (curr1 != null && curr2 != null) { if (curr1.left == null && curr2.right == null) { if (curr1.data != curr2.data) return false; curr1 = curr1.right; curr2 = curr2.left; } else if (curr1.left != null && curr2.right != null) { Node pre1 = curr1.left; Node pre2 = curr2.right; while (pre1.right != null && pre1.right != curr1 && pre2.left != null && pre2.left != curr2) { pre1 = pre1.right; pre2 = pre2.left; } if (pre1.right == null && pre2.left == null) { // Here, we are threading the Node pre1.right = curr1; pre2.left = curr2; curr1 = curr1.left; curr2 = curr2.right; } else if (pre1.right == curr1 && pre2.left == curr2) { // Unthreading the nodes pre1.right = null; pre2.left = null; if (curr1.data != curr2.data) return false; curr1 = curr1.right; curr2 = curr2.left; } else return false; } else return false; } if (curr1 != curr2) return false; return true;}// Driver Codepublic static void Main(String[] args){ /* 5 / \ 3 3 / \ / \ 8 9 9 8 */ // Creation of Binary tree Node root = new Node(5); root.left = new Node(3); root.right = new Node(3); root.left.left = new Node(8); root.left.right = new Node(9); root.right.left = new Node(9); root.right.right = new Node(8); if (isSymmetric(root)) Console.Write("Symmetric"); else Console.Write("Not Symmetric");}}// This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript implementation to check // if Tree is symmetric or not // A Binary Tree Node class Node { constructor(val) { this.left = null; this.right = null; this.data = val; } } // Function to check if the given // binary tree is Symmetric or not function isSymmetric(root) { let curr1 = root, curr2 = root; // Loop to traverse the tree in // Morris Traversal and // Reverse Morris Traversal while (curr1 != null && curr2 != null) { if (curr1.left == null && curr2.right == null) { if (curr1.data != curr2.data) return false; curr1 = curr1.right; curr2 = curr2.left; } else if (curr1.left != null && curr2.right != null) { let pre1 = curr1.left; let pre2 = curr2.right; while (pre1.right != null && pre1.right != curr1 && pre2.left != null && pre2.left != curr2) { pre1 = pre1.right; pre2 = pre2.left; } if (pre1.right == null && pre2.left == null) { // Here, we are threading the Node pre1.right = curr1; pre2.left = curr2; curr1 = curr1.left; curr2 = curr2.right; } else if (pre1.right == curr1 && pre2.left == curr2) { // Unthreading the nodes pre1.right = null; pre2.left = null; if (curr1.data != curr2.data) return false; curr1 = curr1.right; curr2 = curr2.left; } else return false; } else return false; } if (curr1 != curr2) return false; return true; } /* 5 / \ 3 3 / \ / \ 8 9 9 8 */ // Creation of Binary tree let root = new Node(5); root.left = new Node(3); root.right = new Node(3); root.left.left = new Node(8); root.left.right = new Node(9); root.right.left = new Node(9); root.right.right = new Node(8); if (isSymmetric(root)) document.write("Symmetric"); else document.write("Not Symmetric"); </script> |
Output:
Symmetric
Time Complexity: Since every edge of the tree is traversed at most two times exactly as in the case of Morris traversal and in the worst case, the same number of extra edges (as input tree) are created and removed. Therefore, the time complexity of this approach is O(N).
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
