Mirror of n-ary Tree

Last Updated : 13 Feb, 2023

Given a Tree where every node contains variable number of children, convert the tree to its mirror. Below diagram shows an example.

nAryMirror

We strongly recommend you to minimize your browser and try this yourself first.
Node of tree is represented as a key and a variable sized array of children pointers. The idea is similar to mirror of Binary Tree. For every node, we first recur for all of its children and then reverse array of children pointers. We can also do these steps in other way, i.e., reverse array of children pointers first and then recur for children.

Below is C++ implementation of above idea.

C++

// C++ program to mirror an n-ary tree
#include <bits/stdc++.h>
using namespace std;
 
// Represents a node of an n-ary tree
struct Node
{
    int key;
    vector<Node *>child;
};
 
// Function to convert a tree to its mirror
void mirrorTree(Node * root)
{
    // Base case: Nothing to do if root is NULL
    if (root==NULL)
        return;
 
    // Number of children of root
    int n = root->child.size();
 
    // If number of child is less than 2 i.e.
    // 0 or 1 we do not need to do anything
    if (n < 2)
        return;
 
    // Calling mirror function for each child
    for (int i=0; i<n; i++)
        mirrorTree(root->child[i]);
 
    // Reverse vector (variable sized array) of child
    // pointers
    reverse(root->child.begin(), root->child.end());
}
 
// Utility function to create a new tree node
Node *newNode(int key)
{
    Node *temp = new Node;
    temp->key = key;
    return temp;
}
 
// Prints the n-ary tree level wise
void printNodeLevelWise(Node * root)
{
    if (root==NULL)
        return;
 
    // Create a queue and enqueue root to it
    queue<Node *>q;
    q.push(root);
 
    // Do level order traversal. Two loops are used
    // to make sure that different levels are printed
    // in different lines
    while (!q.empty())
    {
        int n = q.size();
        while (n>0)
        {
            // Dequeue an item from queue and print it
            Node * p = q.front();
            q.pop();
            cout << p->key << " ";
 
            // Enqueue all childrent of the dequeued item
            for (int i=0; i<p->child.size(); i++)
                q.push(p->child[i]);
            n--;
        }
 
        cout << endl; // Separator between levels
    }
}
 
// Driver program
int main()
{
    /*   Let us create below tree
    *              10
    *        /   /    \   \
    *        2  34    56   100
    *                 |   /  | \
    *                 1   7  8  9
    */
    Node *root = newNode(10);
    (root->child).push_back(newNode(2));
    (root->child).push_back(newNode(34));
    (root->child).push_back(newNode(56));
    (root->child).push_back(newNode(100));
    (root->child[2]->child).push_back(newNode(1));
    (root->child[3]->child).push_back(newNode(7));
    (root->child[3]->child).push_back(newNode(8));
    (root->child[3]->child).push_back(newNode(9));
 
    cout << "Level order traversal Before Mirroring\n";
    printNodeLevelWise(root);
 
    mirrorTree(root);
 
    cout << "\nLevel order traversal After Mirroring\n";
    printNodeLevelWise(root);
 
    return 0;
}

Java

// Java code for the above approach
import java.util.*;
 
// Represents a node of an n-ary tree
class Node
{
  int key;
  List<Node> child;
  public Node(int key)
  {
    this.key = key;
    child = new ArrayList<Node>();
  }
}
 
class Main
{
 
  // Function to convert a tree to its mirror
  static void mirrorTree(Node root)
  {
 
    // Base case: Nothing to do if root is NULL
    if (root == null)
      return;
 
    // Number of children of root
    int n = root.child.size();
 
    // If number of child is less than 2 i.e.
    // 0 or 1 we do not need to do anything
    if (n < 2)
      return;
 
    // Calling mirror function for each child
    for (int i = 0; i < n; i++)
      mirrorTree(root.child.get(i));
 
    // Reverse vector (variable sized array) of child
    // pointers
    Collections.reverse(root.child);
  }
 
  // Utility function to create a new tree node
  public static Node newNode(int key)
  {
    Node temp = new Node(key);
    return temp;
  }
 
  // Prints the n-ary tree level wise
  static void printNodeLevelWise(Node root)
  {
    if (root == null)
      return;
 
    // Create a queue and enqueue root to it
    Queue<Node> q = new LinkedList<Node>();
    q.add(root);
 
    // Do level order traversal. Two loops are used
    // to make sure that different levels are printed
    // in different lines
    while (!q.isEmpty())
    {
      int n = q.size();
      while (n > 0)
      {
        // Dequeue an item from queue and print it
        Node p = q.poll();
        System.out.print(p.key + " ");
 
        // Enqueue all childrent of the dequeued item
        for (int i = 0; i < p.child.size(); i++)
          q.add(p.child.get(i));
        n--;
      }
 
      System.out.println(); // Separator between levels
    }
  }
 
  // Driver program
  public static void main(String[] args)
  {
    /*   Let us create below tree
        *              10
        *        /   /    \   \
        *        2  34    56   100
        *                 |   /  | \
        *                 1   7  8  9
        */
    Node root = newNode(10);
    root.child.add(newNode(2));
    root.child.add(newNode(34));
    root.child.add(newNode(56));
    root.child.add(newNode(100));
    root.child.get(2).child.add(newNode(1));
    root.child.get(3).child.add(newNode(7));
    root.child.get(3).child.add(newNode(8));
    root.child.get(3).child.add(newNode(9));
 
    System.out.println("Level order traversal Before Mirroring");
    printNodeLevelWise(root);
 
    mirrorTree(root);
 
    System.out.println("\nLevel order traversal After Mirroring");
    printNodeLevelWise(root);
  }
}
 
// This code is contributed by lokeshpotta20.

Python3

# Python program to mirror an n-ary tree
 
# Represents a node of an n-ary tree
class Node :
 
    # Utility function to create a new tree node
    def __init__(self ,key):
        self.key = key 
        self.child = []
 
 
# Function to convert a tree to its mirror
def mirrorTree(root):
     
    # Base Case : nothing to do if root is None
    if root is None:
        return
     
    # Number of children of root 
    n = len(root.child)
 
    # If number of child is less than 2 i.e. 
    # 0 or 1 we don't need to do anything
    if n <2 :
        return
     
    # Calling mirror function for each child
    for i in range(n):
        mirrorTree(root.child[i]);
     
    # Reverse variable sized array of child pointers
    root.child.reverse()
     
 
# Prints the n-ary tree level wise
 
def printNodeLevelWise(root):
    if root is None:
        return
     
    # create a queue and enqueue root to it
    queue = []
    queue.append(root)
 
    # Do level order traversal. Two loops are used
    # to make sure that different levels are printed
    # in different lines
    while(len(queue) >0):
 
        n = len(queue)
        while(n > 0) :
 
            # Dequeue an item from queue and print it
            p = queue[0]
            queue.pop(0)
            print(p.key,end=" ")
     
            # Enqueue all children of the dequeued item
            for index, value in enumerate(p.child):
                queue.append(value)
 
            n -= 1
        print() # Separator between levels
         
 
# Driver Program
 
    """   Let us create below tree
    *              10
    *        /   /    \   \
    *        2  34    56   100
    *                 |   /  | \
    *                 1   7  8  9
    """
 
root = Node(10)
root.child.append(Node(2))
root.child.append(Node(34))
root.child.append(Node(56))
root.child.append(Node(100))
root.child[2].child.append(Node(1))
root.child[3].child.append(Node(7))
root.child[3].child.append(Node(8))
root.child[3].child.append(Node(9))
 
print ("Level order traversal Before Mirroring")
printNodeLevelWise(root)
 
mirrorTree(root)
     
print ("\nLevel Order traversal After Mirroring")
printNodeLevelWise(root)

C#

// C# code for the above approach
using System;
using System.Collections.Generic;
 
// Represents a node of an n-ary tree
public class Node {
  public int key;
  public List<Node> child;
 
  public Node(int key)
  {
    this.key = key;
    child = new List<Node>();
  }
}
 
public class GFG {
 
  // Function to convert a tree to its mirror
  static void MirrorTree(Node root)
  {
    // Base case: Nothing to do if root is NULL
    if (root == null)
      return;
 
    // Number of children of root
    int n = root.child.Count;
 
    // If number of child is less than 2 i.e.
    // 0 or 1 we do not need to do anything
    if (n < 2)
      return;
 
    // Calling mirror function for each child
    for (int i = 0; i < n; i++)
      MirrorTree(root.child[i]);
 
    // Reverse list of child
    root.child.Reverse();
  }
 
  // Utility function to create a new tree node
  public static Node NewNode(int key)
  {
    Node temp = new Node(key);
    return temp;
  }
 
  // Prints the n-ary tree level wise
  static void PrintNodeLevelWise(Node root)
  {
    if (root == null)
      return;
 
    // Create a queue and enqueue root to it
    Queue<Node> q = new Queue<Node>();
    q.Enqueue(root);
 
    // Do level order traversal. Two loops are used
    // to make sure that different levels are printed
    // in different lines
    while (q.Count > 0) {
      int n = q.Count;
      while (n > 0) {
        // Dequeue an item from queue and print it
        Node p = q.Dequeue();
        Console.Write(p.key + " ");
 
        // Enqueue all children of the dequeued item
        for (int i = 0; i < p.child.Count; i++)
          q.Enqueue(p.child[i]);
        n--;
      }
 
      Console.WriteLine(); // Separator between levels
    }
  }
 
  static public void Main()
  {
 
    /* Let us create below tree
         *           10
         *     / / \ \
         *     2 34 56 100
         *             | / | \
         *             1 7 8 9
         */
    Node root = NewNode(10);
    root.child.Add(NewNode(2));
    root.child.Add(NewNode(34));
    root.child.Add(NewNode(56));
    root.child.Add(NewNode(100));
    root.child[2].child.Add(NewNode(1));
    root.child[3].child.Add(NewNode(7));
    root.child[3].child.Add(NewNode(8));
    root.child[3].child.Add(NewNode(9));
 
    Console.WriteLine(
      "Level order traversal Before Mirroring");
    PrintNodeLevelWise(root);
    MirrorTree(root);
 
    Console.WriteLine(
      "\nLevel order traversal After Mirroring");
    PrintNodeLevelWise(root);
  }
}
 
// This code is contributed by lokeshmvs21.

Javascript

<script>
  
// Javascript program to mirror an n-ary tree
 
// Represents a node of an n-ary tree
class Node
{
  constructor()
  {
    this.key = 0;
    this.child = []
  }
};
 
// Function to convert a tree to its mirror
function mirrorTree(root)
{
    // Base case: Nothing to do if root is null
    if (root==null)
        return;
 
    // Number of children of root
    var n = root.child.length;
 
    // If number of child is less than 2 i.e.
    // 0 or 1 we do not need to do anything
    if (n < 2)
        return;
 
    // Calling mirror function for each child
    for(var i=0; i<n; i++)
        mirrorTree(root.child[i]);
 
    // Reverse vector (variable sized array) of child
    // pointers
    root.child.reverse();
}
 
// Utility function to create a new tree node
function newNode(key)
{
    var temp = new Node;
    temp.key = key;
    return temp;
}
 
// Prints the n-ary tree level wise
function printNodeLevelWise(root)
{
    if (root==null)
        return;
 
    // Create a queue and enqueue root to it
    var q = [];
    q.push(root);
 
    // Do level order traversal. Two loops are used
    // to make sure that different levels are printed
    // in different lines
    while (q.length!=0)
    {
        var n = q.length;
        while (n>0)
        {
            // Dequeue an item from queue and print it
            var p = q[0];
            q.shift();
            document.write( p.key + " ");
 
            // Enqueue all childrent of the dequeued item
            for(var i=0; i<p.child.length; i++)
                q.push(p.child[i]);
            n--;
        }
 
        document.write("<br>") // Separator between levels
    }
}
 
// Driver program
/*   Let us create below tree
*              10
*        /   /    \   \
*        2  34    56   100
*                 |   /  | \
*                 1   7  8  9
*/
var root = newNode(10);
(root.child).push(newNode(2));
(root.child).push(newNode(34));
(root.child).push(newNode(56));
(root.child).push(newNode(100));
(root.child[2].child).push(newNode(1));
(root.child[3].child).push(newNode(7));
(root.child[3].child).push(newNode(8));
(root.child[3].child).push(newNode(9));
document.write("Level order traversal Before Mirroring<br>");
printNodeLevelWise(root);
mirrorTree(root);
document.write("<br>Level order traversal After Mirroring<br>");
printNodeLevelWise(root);
 
// This code is contributed by rrrtnx.
</script>

Output

Level order traversal Before Mirroring
10 
2 34 56 100 
1 7 8 9 

Level order traversal After Mirroring
10 
100 56 34 2 
9 8 7 1

Time Complexity: O(N) here N is number of nodes

Auxiliary Space: O(N) ,here N is number of nodes

GeeksforGeeks

Improve

Previous Article

Depth of an N-Ary tree

Insertion in n-ary tree in given order and Level order traversal

Similar Reads

Check mirror in n-ary tree

Given two n-ary trees, the task is to check if they are the mirror of each other or not. Print "Yes" if they are the mirror of each other else "No". Examples: Input : Node = 3, Edges = 2 Edge 1 of first N-ary: 1 2 Edge 2 of first N-ary: 1 3 Edge 1 of second N-ary: 1 3 Edge 2 of second N-ary: 1 2 Output : Yes Input : Node = 3, Edges = 2 Edge 1 of fi

Check if a number is prime in Flipped Upside Down, Mirror Flipped and Mirror Flipped Upside Down

Given an integer N, the task is to check if N is a prime number in Flipped Down, Mirror Flipped and Mirror Flipped Down forms of the given number.Examples: Input: N = 120121 Output: YesExplanation: Flipped forms of the number:Flipped Upside Down - 151051Mirror Flipped - 121021Mirror Upside Down - 150151Since 1510151 and 121021 are both prime number

Convert a Binary Tree into its Mirror Tree (Invert Binary Tree)

Given a binary tree, the task is to convert the binary tree into its Mirror tree. Mirror of a Binary Tree T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged. Recommended PracticeMirror TreeTry It!The idea is to traverse recursively and swap the right and left subtrees after traversing the subtrees. Follow

Create a mirror tree from the given binary tree

Given a binary tree, the task is to create a new binary tree which is a mirror image of the given binary tree. Examples: Input: 5 / \ 3 6 / \ 2 4 Output: Inorder of original tree: 2 3 4 5 6 Inorder of mirror tree: 6 5 4 3 2 Mirror tree will be: 5 / \ 6 3 / \ 4 2 Input: 2 / \ 1 8 / \ 12 9 Output: Inorder of original tree: 12 1 2 8 9 Inorder of mirro

Construct Full Binary Tree using its Preorder traversal and Preorder traversal of its mirror tree

Given two arrays that represent Preorder traversals of a full binary tree and its mirror tree, we need to write a program to construct the binary tree using these two Preorder traversals.A Full Binary Tree is a binary tree where every node has either 0 or 2 children. Note: It is not possible to construct a general binary tree using these two traver

Build a segment tree for N-ary rooted tree

Prerequisite: Segment tree and depth first search.In this article, an approach to convert an N-ary rooted tree( a tree with more than 2 children) into a segment tree is discussed which is used to perform a range update queries. Why do we need a segment tree when we already have an n-ary rooted tree? Many times, a situation occurs where the same ope

Check if the given n-ary tree is a binary tree

Given an n-ary tree, the task is to check whether the given tree is binary or not. Examples: Input: A / \ B C / \ \ D E F Output: Yes Input: A / | \ B C D \ F Output: No Approach: Every node in a binary tree can have at most 2 children. So, for every node of the given tree, count the number of children and if for any node the count exceeds 2 then p

Remove all leaf nodes from a Generic Tree or N-ary Tree

Given a Generic tree, the task is to delete the leaf nodes from the tree. Examples: Input: 5 / / \ \ 1 2 3 8 / / \ \ 15 4 5 6 Output: 5 : 1 2 3 1 : 2 : 3 : Explanation: Deleted leafs are: 8, 15, 4, 5, 6 Input: 8 / | \ 9 7 2 / | \ | / / | \ \ 4 5 6 10 11 1 2 2 3 Output: 8: 9 7 2 9: 7: 2: Approach: Follow the steps given below to solve the problem Co

Count of nodes in given N-ary tree such that their subtree is a Binary Tree

Given an N-ary tree root, the task is to find the count of nodes such that their subtree is a binary tree. Example: Input: Tree in the image below Output: 11Explanation: The nodes such that there subtree is a binary tree are {2, 8, 10, 6, 7, 3, 1, 9, 5, 11, 12}. Input: Tree in the image below Output: 9 Approach: The given problem can be solved by u

Tree of Space - Locking and Unlocking N-Ary Tree

Given a world map in the form of Generic M-ary Tree consisting of N nodes and an array queries[], the task is to implement the functions Lock, Unlock and Upgrade for the given tree. For each query in queries[], the functions return true when the operation is performed successfully, otherwise it returns false. The functions are defined as: X: Name o

Article Tags :

Practice Tags :

Tree