Given an m-ary tree, write an efficient algorithm to convert the tree to its mirror.
An m-ary tree (aka k-ary tree) is a tree in which each node has no more than m children. Each node of an m-ary tree has an array for storing pointers to each of its children.
The binary tree and the ternary tree are special cases of the m-ary tree where m = 2 and m = 3. Consider the following diagram, which displays an m-ary tree with m = 5.
The following m-ary tree is a mirror image of the above tree.
Convert binary tree to its mirror
The idea is similar to the above post – Traverse the tree in postorder fashion and for every node, first recursively convert its children to mirror, and then reverse the array storing pointers to each of its children. The preorder traversal would also work here.
Traversing an m-ary tree is very similar to binary tree traversal. The post-order traversal of a binary tree visits the left subtree first, followed by the right subtree, and the parent node is processed at last. Since there are m children per node in an m-ary tree, the post-order traversal visits the 1st child first, followed by the 2nd child, …, all the way till the m’th child. After processing all children, processes the parent node.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Data structure to store m-ary tree nodes
struct Node
{
int data;
vector<Node*> child;
Node(int data) {
this->data = data;
}
};
// Traverse and print an m-ary tree using pre-order traversal
void printTree(Node *root)
{
// base case
if (root == nullptr) {
return;
}
// print the current node
cout << root->data << ‘ ‘;
// recur for all children nodes from left to right
for (Node* child: root->child) {
printTree(child);
}
}
// Recursive function to convert an m-ary tree to its mirror image
void convertToMirror(Node *root)
{
// base case
if (root == nullptr) {
return;
}
// recur for each children
for (Node* child: root->child) {
convertToMirror(child);
}
// Reverse the order of the elements in the children
reverse(root->child.begin(), root->child.end());
/*
// std::reverse is equivalent to below code
for (int i = 0, j = (root->child).size() – 1; i < j; i++, j–) {
swap(root->child[i], root->child[j]);
}
*/
}
int main()
{
// construct an m-ary tree
Node *root = new Node(1);
(root->child).push_back(new Node(2));
(root->child).push_back(new Node(3));
(root->child).push_back(new Node(4));
(root->child).push_back(new Node(5));
(root->child).push_back(new Node(6));
(root->child[0]->child).push_back(new Node(7));
(root->child[0]->child).push_back(new Node(8));
(root->child[0]->child).push_back(new Node(9));
(root->child[2]->child).push_back(new Node(10));
(root->child[2]->child).push_back(new Node(11));
(root->child[2]->child).push_back(new Node(12));
(root->child[4]->child).push_back(new Node(13));
(root->child[4]->child).push_back(new Node(14));
(root->child[0]->child[1]->child).push_back(new Node(15));
(root->child[0]->child[1]->child).push_back(new Node(16));
(root->child[4]->child[0]->child).push_back(new Node(17));
(root->child[4]->child[0]->child).push_back(new Node(18));
(root->child[4]->child[0]->child).push_back(new Node(19));
(root->child[4]->child[0]->child).push_back(new Node(20));
convertToMirror(root);
printTree(root);
return 0;
}
|
Output:
1 6 14 13 20 19 18 17 5 4 12 11 10 3 2 9 8 16 15 7
Java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
import java.util.ArrayList;
import java.util.List;
// Data structure to store m-ary tree nodes
class Node
{
int data;
List<Node> child;
Node(int data) {
this.data = data;
child = new ArrayList<>();
}
}
class Main
{
// Traverse and print an m-ary tree using pre-order traversal
public static void printTree(Node root)
{
// base case
if (root == null) {
return;
}
// print the current node
System.out.print(root.data + ” “);
// recur for all children nodes from left to right
for (Node child: root.child) {
printTree(child);
}
}
// Recursive function to convert an m-ary tree to its mirror image
public static void convertToMirror(Node root)
{
// base case
if (root == null) {
return;
}
// recur for each children
for (Node child: root.child) {
convertToMirror(child);
}
// Reverse the order of the elements in the children
int n = root.child.size();
for (int i = 0, j = n – 1; i < j; i++, j—) {
Node temp = root.child.get(i);
root.child.set(i, root.child.get(j));
root.child.set(j, temp);
}
}
public static void main(String[] args)
{
// construct an m-ary tree
Node root = new Node(1);
(root.child).add(new Node(2));
(root.child).add(new Node(3));
(root.child).add(new Node(4));
(root.child).add(new Node(5));
(root.child).add(new Node(6));
(root.child.get(0).child).add(new Node(7));
(root.child.get(0).child).add(new Node(8));
(root.child.get(0).child).add(new Node(9));
(root.child.get(2).child).add(new Node(10));
(root.child.get(2).child).add(new Node(11));
(root.child.get(2).child).add(new Node(12));
(root.child.get(4).child).add(new Node(13));
(root.child.get(4).child).add(new Node(14));
(root.child.get(0).child.get(1).child).add(new Node(15));
(root.child.get(0).child.get(1).child).add(new Node(16));
(root.child.get(4).child.get(0).child).add(new Node(17));
(root.child.get(4).child.get(0).child).add(new Node(18));
(root.child.get(4).child.get(0).child).add(new Node(19));
(root.child.get(4).child.get(0).child).add(new Node(20));
convertToMirror(root);
printTree(root);
}
}
|
Output:
1 6 14 13 20 19 18 17 5 4 12 11 10 3 2 9 8 16 15 7
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
# Data structure to store m-ary tree nodes
class Node:
def __init__(self, data):
self.data = data
self.child = list()
# Traverse and print an m-ary tree using pre-order traversal
def printTree(root):
# base case
if root is None:
return
# print the current node
print(root.data, end=‘ ‘)
# recur for all children nodes from left to right
for c in root.child:
printTree(c)
# Recursive function to convert an m-ary tree to its mirror image
def swap(child, i, j):
x = child[i]
child[i] = child[j]
child[j] = x
def convertToMirror(root):
# base case
if root is None:
return
# recur for each children
for c in root.child:
convertToMirror(c)
# Reverse the order of the elements in the children
n = len(root.child)
for i in range(n//2):
swap(root.child, i, n – i – 1)
if __name__ == ‘__main__’:
# construct an m-ary tree
root = Node(1)
(root.child).append(Node(2))
(root.child).append(Node(3))
(root.child).append(Node(4))
(root.child).append(Node(5))
(root.child).append(Node(6))
(root.child[0].child).append(Node(7))
(root.child[0].child).append(Node(8))
(root.child[0].child).append(Node(9))
(root.child[2].child).append(Node(10))
(root.child[2].child).append(Node(11))
(root.child[2].child).append(Node(12))
(root.child[4].child).append(Node(13))
(root.child[4].child).append(Node(14))
(root.child[0].child[1].child).append(Node(15))
(root.child[0].child[1].child).append(Node(16))
(root.child[4].child[0].child).append(Node(17))
(root.child[4].child[0].child).append(Node(18))
(root.child[4].child[0].child).append(Node(19))
(root.child[4].child[0].child).append(Node(20))
convertToMirror(root)
printTree(root)
|
Output:
1 6 14 13 20 19 18 17 5 4 12 11 10 3 2 9 8 16 15 7
Download Run Code
Output:
1 6 14 13 20 19 18 17 5 4 12 11 10 3 2 9 8 16 15 7
Download Run Code
Output:
1 6 14 13 20 19 18 17 5 4 12 11 10 3 2 9 8 16 15 7
Download Run Code
Output:
1 6 14 13 20 19 18 17 5 4 12 11 10 3 2 9 8 16 15 7
The time complexity of above solution is O(n) and need O(h) extra space for the call stack where h is the height of the tree.
source