Given an N-ary tree root, the task is to check if it is symmetric horizontally (Mirror image of itself).
Example:
Input: root = 7
/ / \ \
4 2 2 4
/ | / | | \ | \
3 2 6 7 7 6 2 3
Output: true
Explanation: The left side of the tree is a mirror image of the right sideInput: root= 2
/ | \
3 4 3
/ | \
5 6 5
Output: true
Approach: The given problem can be solved by using the preorder traversal. The idea is to pass two root nodes as parameters and check if the value of the current nodes is the same and use recursion to check if the value of children of the left node is the same as the values of children of the right node.
Below steps can be followed to solve the problem:
- Apply pre-order traversal on the N-ary tree:
- Check if the value of both the root nodes is the same or not.
- Also, check if the number of nodes of both the roots is the same or not
- Iterate the children node of the left root from left to right and simultaneously iterate the nodes of the right node from right to left and use recursion.
Below is the implementation of the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;class Node{public: vector<Node *> children; int val; // constructor Node(int v) { val = v; children = {}; }};// Preorder traversal to check// if the generic tree// is symmetric or notbool preorder( Node *root1, Node *root2){ // If the values of both the // root is not the same or if // the number of children are // not the same then return false if (root1->val != root2->val || root1->children.size() != root2->children.size()) return false; // Number of children int size = root1->children.size(); // Iterate left to right on // left root and right to left // on the right root for (int i = 0; i < (size+1)/2; i++) { // If any one branch is not // symmetric then return false if (!preorder( root1->children[i], root2->children[size - 1 - i])) return false; } // Tree is symmetric return true return true;}// Function to check if the generic// tree is symmetric or notbool isSymmetric(Node *root){ // Base case if (root == NULL) return true; // Apply preorder traversal // on the tree return preorder(root, root);}// Driver codeint main(){ // Initialize the tree Node *seven = new Node(7); Node *five1 = new Node(5); Node *five2 = new Node(5); Node *four = new Node(4); seven->children.push_back(five1); seven->children.push_back(four); seven->children.push_back(five2); // Call the function // and print the result if (isSymmetric(seven)) { cout << "true" << endl; } else { cout << "false" << endl; } return 0;}// This code is contributed by Potta Lokesh |
Java
// Java implementation for the above approachimport java.io.*;import java.util.*;class GFG { // Function to check if the generic // tree is symmetric or not public static boolean isSymmetric(Node root) { // Base case if (root == null) return true; // Apply preorder traversal // on the tree return preorder(root, root); } // Preorder traversal to check // if the generic tree // is symmetric or not public static boolean preorder( Node root1, Node root2) { // If the values of both the // root is not the same or if // the number of children are // not the same then return false if (root1.val != root2.val || root1.children.size() != root2.children.size()) return false; // Number of children int size = root1.children.size(); // Iterate left to right on // left root and right to left // on the right root for (int i = 0; i < size; i++) { // If any one branch is not // symmetric then return false if (!preorder( root1.children.get(i), root2.children.get(size - 1 - i))) return false; } // Tree is symmetric return true return true; } // Driver code public static void main(String[] args) { // Initialize the tree Node seven = new Node(7); Node five1 = new Node(5); Node five2 = new Node(5); Node four = new Node(4); seven.children.add(five1); seven.children.add(four); seven.children.add(five2); // Call the function // and print the result System.out.println( isSymmetric(seven)); } static class Node { List<Node> children; int val; // constructor public Node(int val) { this.val = val; children = new ArrayList<>(); } }} |
Python3
# Python code for the above approachclass Node: def __init__(self, val): self.val = val self.children = []# Preorder traversal to check# if the generic tree# is symmetric or notdef preorder(root1, root2): # If the values of both the # root is not the same or if # the number of children are # not the same then return false if (root1.val != root2.val or len(root1.children) != len(root2.children)): return False # Number of children size = len(root1.children) # Iterate left to right on # left root and right to left # on the right root for i in range(0, (size + 1)//2): # If any one branch is not # symmetric then return false if (preorder(root1.children[i], root2.children[size - 1 - i]) == False): return False # Tree is symmetric return true return True# Function to check if the generic# tree is symmetric or notdef isSymmetric(root): # Base case if (root == None): return True # Apply preorder traversal # on the tree return preorder(root, root)# Driver code# Initialize the treeseven = Node(7)five1 = Node(5)five2 = Node(5)four = Node(4)seven.children.append(five1)seven.children.append(four)seven.children.append(five2)# Call the function# and print the resultif (isSymmetric(seven)): print("True")else: print("False") # This code is contributed by rj13to. |
C#
// C# implementation for the above approachusing System;using System.Collections.Generic;public class GFG { // Function to check if the generic // tree is symmetric or not static bool isSymmetric(Node root) { // Base case if (root == null) return true; // Apply preorder traversal // on the tree return preorder(root, root); } // Preorder traversal to check // if the generic tree // is symmetric or not static bool preorder( Node root1, Node root2) { // If the values of both the // root is not the same or if // the number of children are // not the same then return false if (root1.val != root2.val || root1.children.Count != root2.children.Count) return false; // Number of children int size = root1.children.Count; // Iterate left to right on // left root and right to left // on the right root for (int i = 0; i < size; i++) { // If any one branch is not // symmetric then return false if (!preorder( root1.children[i], root2.children[size - 1 - i])) return false; } // Tree is symmetric return true return true; } // Driver code public static void Main(String[] args) { // Initialize the tree Node seven = new Node(7); Node five1 = new Node(5); Node five2 = new Node(5); Node four = new Node(4); seven.children.Add(five1); seven.children.Add(four); seven.children.Add(five2); // Call the function // and print the result Console.WriteLine( isSymmetric(seven)); } class Node { public List<Node> children; public int val; // constructor public Node(int val) { this.val = val; children = new List<Node>(); } }}// This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript code for the above approachclass Node { // constructor constructor(v) { this.val = v; this.children = []; }};// Preorder traversal to check// if the generic tree// is symmetric or notfunction preorder(root1, root2) { // If the values of both the // root is not the same or if // the number of children are // not the same then return false if (root1.val != root2.val || root1.children.length != root2.children.length) return false; // Number of children let size = root1.children.length; // Iterate left to right on // left root and right to left // on the right root for (let i = 0; i < size; i++) { // If any one branch is not // symmetric then return false if (!preorder( root1.children[i], root2.children[size - 1 - i])) return false; } // Tree is symmetric return true return true;}// Function to check if the generic// tree is symmetric or notfunction isSymmetric(root) { // Base case if (root == null) return true; // Apply preorder traversal // on the tree return preorder(root, root);}// Driver code// Initialize the treelet seven = new Node(7);let five1 = new Node(5);let five2 = new Node(5);let four = new Node(4);seven.children.push(five1);seven.children.push(four);seven.children.push(five2);// Call the function// and print the resultif (isSymmetric(seven)) { document.write("true");}else { document.write("false");}// This code is contributed by gfgking. </script> |
Output
true
Time Complexity: O(N), where N is the number of nodes in the tree
Auxiliary Space: O(H), Where H is the height of the tree
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!
