Create a mirror of an m–ary Tree

Problem

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

Sample Input

Sample Output

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);
        (root.children).add(new TreeNode(2));
        (root.children).add(new TreeNode(3));
        (root.children).add(new TreeNode(4));

        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:

• Construction of an Expression Tree
• Diameter of a Binary Tree
• Subset Sum Problem
• Bottom View of a Binary Tree
• Reverse a Linked List
• Clone a Singly Linked List
• AVL Tree
• DSA Binary Search Tree
• Tree Data Structure & Algorithm