# Create a mirror of an m–ary Tree

Posted in

Vinay Khatri
Last updated on September 8, 2024

## Problem

Given an m-ary tree that can have a count of children greater than 2. Convert it into its mirror tree .

## Approach

We can use “Depth First Search” to solve this problem. We can first store all the children of each node in a list. We traverse the given tree in any order and for each node reverse its children list.  The reversal can be done when we backtrack.

### Complexity Analysis

The time complexity would be O(N) and the space complexity would also be O(N) due to the call stack.

### C++ Programming

```#include<bits/stdc++.h>
using namespace std;

struct TreeNode
{
int val;
vector<TreeNode*> children;

TreeNode(int val) {
this->val = val;
}
};

// print the tree
void preOrder(TreeNode* root)
{
// base case
if (root == nullptr) {
return;
}

cout << root->val << ' ';
for (TreeNode* children: root->children) {
preOrder(children);
}
}

void solve(TreeNode* root)
{
// base case
if (!root) {
return;
}

// DFS on each child
for (TreeNode* children: root->children) {
solve(children);
}

// Reverse the order of the elements in the children
reverse(root->children.begin(), root->children.end());
}

int main()
{
TreeNode* root = new TreeNode(1);
(root->children).push_back(new TreeNode(2));
(root->children).push_back(new TreeNode(3));
(root->children).push_back(new TreeNode(4));

solve(root);
preOrder(root);

return 0;
}```

#### Output

`1 4 3 2`

### Java Programming

```import java.util.ArrayList;
import java.util.List;

class TreeNode
{
int val;
List<TreeNode> children;

TreeNode(int val)
{
this.val = val;
children = new ArrayList<>();
}
}

class Main
{
public static void inOrder(TreeNode root)
{
// base case
if (root == null) {
return;
}

// print the current node
System.out.print(root.val + " ");

for (TreeNode children: root.children) {
inOrder(children);
}
}

public static void solve(TreeNode root)
{
// base case
if (root == null) {
return;
}

// DFS on all children
for (TreeNode children: root.children) {
solve(children);
}

// Reverse the order of the elements in the children
int n = root.children.size();
for (int i = 0, j = n - 1; i < j; i++, j--)
{
TreeNode temp = root.children.get(i);
root.children.set(i, root.children.get(j));
root.children.set(j, temp);
}
}

public static void main(String[] args)
{
// construct an m–ary tree
TreeNode root = new TreeNode(1);

solve(root);

inOrder(root);
}
}```

#### Output

```1 4 3 2
```

### Python Programming

```class TreeNode:
def __init__(self, val):
self.val = val
self.children = list()

def preOrder(root):
# base case
if root is None:
return

# print the current node
print(root.val, end=' ')

# recur for all children nodes from left to right
for c in root.children:
preOrder(c)

# Recursive function to convert an m–ary tree into its mirror image
def swap(children, i, j):
x = children[i]
children[i] = children[j]
children[j] = x

def solve(root):
# base case
if root is None:
return

# DFS for each children
for c in root.children:
solve(c)

# Reverse the order of the elements in the children
n = len(root.children)

for i in range(n//2):
swap(root.children, i, n - i - 1)

root = TreeNode(1)

(root.children).append(TreeNode(2))
(root.children).append(TreeNode(3))
(root.children).append(TreeNode(4))
solve(root)
preOrder(root)```

#### Output

`1 4 3 2`

People are also reading: