Create a mirror of an m–ary tree
Given an m–ary tree, write an efficient algorithm to convert the tree into 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:
Related Post:
The idea is similar to the above post – Traverse the tree in a 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 postorder traversal on 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 postorder 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 93 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; // Data structure to store an m–ary tree node struct Node { int data; vector<Node*> child; Node(int data) { this->data = data; } }; // Traverse and print an m–ary tree using preorder 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 into its mirror image void convertToMirror(Node* root) { // base case if (root == nullptr) { return; } // recur for each child 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 the following 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 91 92 |
import java.util.ArrayList; import java.util.List; // A class to store an m–ary tree node 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 preorder 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 into its mirror image public static void convertToMirror(Node root) { // base case if (root == null) { return; } // recur for each child 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 76 77 78 |
# A class to store an m–ary tree node class Node: def __init__(self, data): self.data = data self.child = list() # Traverse and print an m–ary tree using preorder 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 into 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 child 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
The time complexity of the above solution is O(n), where n is the total number of nodes in the binary tree. The program requires O(h) extra space for the call stack, where h is the height of the tree.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)