Create a mirror of an m–ary Tree

Posted in

Create a mirror of an m–ary Tree

Vinay Khatri
Last updated on September 19, 2022

    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:

    Tags:
    tree

    Leave a Comment on this Post

    0 Comments