{"id":"896aa99b-c643-4af2-81db-7667e5072d97","name":"Mirror A Generic Tree","description":"1. You are given a partially written GenericTree class.\r\n2. You are required to complete the body of mirror function. The function is expected to create a mirror image of the tree. For more details, check out the question video.\r\n3. Input and Output is managed for you.","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"None","sampleCode":{"cpp":{"code":"int main(){\r\n return 0;\r\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n private static class Node {\r\n int data;\r\n ArrayList<Node> children = new ArrayList<>();\r\n }\r\n\r\n public static void display(Node node) {\r\n String str = node.data + \" -> \";\r\n for (Node child : node.children) {\r\n str += child.data + \", \";\r\n }\r\n str += \".\";\r\n System.out.println(str);\r\n\r\n for (Node child : node.children) {\r\n display(child);\r\n }\r\n }\r\n\r\n public static Node construct(int[] arr) {\r\n Node root = null;\r\n\r\n Stack<Node> st = new Stack<>();\r\n for (int i = 0; i < arr.length; i++) {\r\n if (arr[i] == -1) {\r\n st.pop();\r\n } else {\r\n Node t = new Node();\r\n t.data = arr[i];\r\n\r\n if (st.size() > 0) {\r\n st.peek().children.add(t);\r\n } else {\r\n root = t;\r\n }\r\n\r\n st.push(t);\r\n }\r\n }\r\n\r\n return root;\r\n }\r\n\r\n public static int size(Node node) {\r\n int s = 0;\r\n\r\n for (Node child : node.children) {\r\n s += size(child);\r\n }\r\n s += 1;\r\n\r\n return s;\r\n }\r\n\r\n public static int max(Node node) {\r\n int m = Integer.MIN_VALUE;\r\n\r\n for (Node child : node.children) {\r\n int cm = max(child);\r\n m = Math.max(m, cm);\r\n }\r\n m = Math.max(m, node.data);\r\n\r\n return m;\r\n }\r\n\r\n public static int height(Node node) {\r\n int h = -1;\r\n\r\n for (Node child : node.children) {\r\n int ch = height(child);\r\n h = Math.max(h, ch);\r\n }\r\n h += 1;\r\n\r\n return h;\r\n }\r\n\r\n public static void traversals(Node node){\r\n System.out.println(\"Node Pre \" + node.data);\r\n\r\n for(Node child: node.children){\r\n System.out.println(\"Edge Pre \" + node.data + \"--\" + child.data);\r\n traversals(child);\r\n System.out.println(\"Edge Post \" + node.data + \"--\" + child.data);\r\n }\r\n\r\n System.out.println(\"Node Post \" + node.data);\r\n }\r\n\r\n public static void levelOrderLinewiseZZ(Node node){\r\n Stack<Node> stack = new Stack<>();\r\n stack.add(node);\r\n\r\n Stack<Node> cstack = new Stack<>();\r\n int level = 0;\r\n\r\n while(stack.size() > 0){\r\n node = stack.pop();\r\n System.out.print(node.data + \" \");\r\n\r\n if(level % 2 == 0){\r\n for(int i = 0; i < node.children.size(); i++){\r\n Node child = node.children.get(i);\r\n cstack.push(child);\r\n }\r\n } else {\r\n for(int i = node.children.size() - 1; i >= 0; i--){\r\n Node child = node.children.get(i);\r\n cstack.push(child);\r\n }\r\n }\r\n\r\n if(stack.size() == 0){\r\n stack = cstack;\r\n cstack = new Stack<>();\r\n level++;\r\n System.out.println();\r\n }\r\n }\r\n }\r\n\r\n public static void mirror(Node node){\r\n // write your code here\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n int n = Integer.parseInt(br.readLine());\r\n int[] arr = new int[n];\r\n String[] values = br.readLine().split(\" \");\r\n for (int i = 0; i < n; i++) {\r\n arr[i] = Integer.parseInt(values[i]);\r\n }\r\n\r\n Node root = construct(arr);\r\n display(root);\r\n mirror(root);\r\n display(root);\r\n }\r\n\r\n}"},"python":{"code":"def main();"}},"points":10,"difficulty":"medium","sampleInput":"24\r\n10 20 50 -1 60 -1 -1 30 70 -1 80 110 -1 120 -1 -1 90 -1 -1 40 100 -1 -1 -1","sampleOutput":"10 -> 20, 30, 40, .\r\n20 -> 50, 60, .\r\n50 -> .\r\n60 -> .\r\n30 -> 70, 80, 90, .\r\n70 -> .\r\n80 -> 110, 120, .\r\n110 -> .\r\n120 -> .\r\n90 -> .\r\n40 -> 100, .\r\n100 -> .\r\n10 -> 40, 30, 20, .\r\n40 -> 100, .\r\n100 -> .\r\n30 -> 90, 80, 70, .\r\n90 -> .\r\n80 -> 120, 110, .\r\n120 -> .\r\n110 -> .\r\n70 -> .\r\n20 -> 60, 50, .\r\n60 -> .\r\n50 -> .","questionVideo":"https://www.youtube.com/embed/CjtGTcG-fUU","hints":[],"associated":[{"id":"ba6d519e-16cf-4a3f-a49b-7ca9ad6c47bb","name":"Only a symmetric tree can have mirror, true or false?","slug":"only-a-symmetric-tree-can-have-mirror-true-or-false","type":4},{"id":"ecf3a5b0-a68b-48e4-b024-1ec37ec42850","name":"What is the minimum number of levels a tree should have for it to have a mirror?","slug":"what-is-the-minimum-number-of-levels-a-tree-should-have-for-it-to-have-a-mirror","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"b6a55c74-7dc3-45b6-a948-9dcbaebf9367","name":"Generic Tree For Beginners","slug":"generic-tree-for-beginners","type":0},{"id":"e1e734c3-a5c7-4292-b324-8f2894459160","name":"Mirror A Generic Tree","slug":"mirror-a-generic-tree","type":1}],"next":{"id":"401af9aa-1923-402d-b676-df21965892b7","name":"Mirror Of A Generic Tree","type":3,"slug":"mirror-of-a-generic-tree"},"prev":{"id":"7e50a09f-e80c-4f93-b683-dc8cfa75eff0","name":"Level Order traversals - More Approaches","type":0,"slug":"level-order-traversals-more-approaches"}}}

Mirror A Generic Tree

1. You are given a partially written GenericTree class. 2. You are required to complete the body of mirror function. The function is expected to create a mirror image of the tree. For more details, check out the question video. 3. Input and Output is managed for you.

{"id":"896aa99b-c643-4af2-81db-7667e5072d97","name":"Mirror A Generic Tree","description":"1. You are given a partially written GenericTree class.\r\n2. You are required to complete the body of mirror function. The function is expected to create a mirror image of the tree. For more details, check out the question video.\r\n3. Input and Output is managed for you.","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"None","sampleCode":{"cpp":{"code":"int main(){\r\n return 0;\r\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n private static class Node {\r\n int data;\r\n ArrayList<Node> children = new ArrayList<>();\r\n }\r\n\r\n public static void display(Node node) {\r\n String str = node.data + \" -> \";\r\n for (Node child : node.children) {\r\n str += child.data + \", \";\r\n }\r\n str += \".\";\r\n System.out.println(str);\r\n\r\n for (Node child : node.children) {\r\n display(child);\r\n }\r\n }\r\n\r\n public static Node construct(int[] arr) {\r\n Node root = null;\r\n\r\n Stack<Node> st = new Stack<>();\r\n for (int i = 0; i < arr.length; i++) {\r\n if (arr[i] == -1) {\r\n st.pop();\r\n } else {\r\n Node t = new Node();\r\n t.data = arr[i];\r\n\r\n if (st.size() > 0) {\r\n st.peek().children.add(t);\r\n } else {\r\n root = t;\r\n }\r\n\r\n st.push(t);\r\n }\r\n }\r\n\r\n return root;\r\n }\r\n\r\n public static int size(Node node) {\r\n int s = 0;\r\n\r\n for (Node child : node.children) {\r\n s += size(child);\r\n }\r\n s += 1;\r\n\r\n return s;\r\n }\r\n\r\n public static int max(Node node) {\r\n int m = Integer.MIN_VALUE;\r\n\r\n for (Node child : node.children) {\r\n int cm = max(child);\r\n m = Math.max(m, cm);\r\n }\r\n m = Math.max(m, node.data);\r\n\r\n return m;\r\n }\r\n\r\n public static int height(Node node) {\r\n int h = -1;\r\n\r\n for (Node child : node.children) {\r\n int ch = height(child);\r\n h = Math.max(h, ch);\r\n }\r\n h += 1;\r\n\r\n return h;\r\n }\r\n\r\n public static void traversals(Node node){\r\n System.out.println(\"Node Pre \" + node.data);\r\n\r\n for(Node child: node.children){\r\n System.out.println(\"Edge Pre \" + node.data + \"--\" + child.data);\r\n traversals(child);\r\n System.out.println(\"Edge Post \" + node.data + \"--\" + child.data);\r\n }\r\n\r\n System.out.println(\"Node Post \" + node.data);\r\n }\r\n\r\n public static void levelOrderLinewiseZZ(Node node){\r\n Stack<Node> stack = new Stack<>();\r\n stack.add(node);\r\n\r\n Stack<Node> cstack = new Stack<>();\r\n int level = 0;\r\n\r\n while(stack.size() > 0){\r\n node = stack.pop();\r\n System.out.print(node.data + \" \");\r\n\r\n if(level % 2 == 0){\r\n for(int i = 0; i < node.children.size(); i++){\r\n Node child = node.children.get(i);\r\n cstack.push(child);\r\n }\r\n } else {\r\n for(int i = node.children.size() - 1; i >= 0; i--){\r\n Node child = node.children.get(i);\r\n cstack.push(child);\r\n }\r\n }\r\n\r\n if(stack.size() == 0){\r\n stack = cstack;\r\n cstack = new Stack<>();\r\n level++;\r\n System.out.println();\r\n }\r\n }\r\n }\r\n\r\n public static void mirror(Node node){\r\n // write your code here\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n int n = Integer.parseInt(br.readLine());\r\n int[] arr = new int[n];\r\n String[] values = br.readLine().split(\" \");\r\n for (int i = 0; i < n; i++) {\r\n arr[i] = Integer.parseInt(values[i]);\r\n }\r\n\r\n Node root = construct(arr);\r\n display(root);\r\n mirror(root);\r\n display(root);\r\n }\r\n\r\n}"},"python":{"code":"def main();"}},"points":10,"difficulty":"medium","sampleInput":"24\r\n10 20 50 -1 60 -1 -1 30 70 -1 80 110 -1 120 -1 -1 90 -1 -1 40 100 -1 -1 -1","sampleOutput":"10 -> 20, 30, 40, .\r\n20 -> 50, 60, .\r\n50 -> .\r\n60 -> .\r\n30 -> 70, 80, 90, .\r\n70 -> .\r\n80 -> 110, 120, .\r\n110 -> .\r\n120 -> .\r\n90 -> .\r\n40 -> 100, .\r\n100 -> .\r\n10 -> 40, 30, 20, .\r\n40 -> 100, .\r\n100 -> .\r\n30 -> 90, 80, 70, .\r\n90 -> .\r\n80 -> 120, 110, .\r\n120 -> .\r\n110 -> .\r\n70 -> .\r\n20 -> 60, 50, .\r\n60 -> .\r\n50 -> .","questionVideo":"https://www.youtube.com/embed/CjtGTcG-fUU","hints":[],"associated":[{"id":"ba6d519e-16cf-4a3f-a49b-7ca9ad6c47bb","name":"Only a symmetric tree can have mirror, true or false?","slug":"only-a-symmetric-tree-can-have-mirror-true-or-false","type":4},{"id":"ecf3a5b0-a68b-48e4-b024-1ec37ec42850","name":"What is the minimum number of levels a tree should have for it to have a mirror?","slug":"what-is-the-minimum-number-of-levels-a-tree-should-have-for-it-to-have-a-mirror","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"b6a55c74-7dc3-45b6-a948-9dcbaebf9367","name":"Generic Tree For Beginners","slug":"generic-tree-for-beginners","type":0},{"id":"e1e734c3-a5c7-4292-b324-8f2894459160","name":"Mirror A Generic Tree","slug":"mirror-a-generic-tree","type":1}],"next":{"id":"401af9aa-1923-402d-b676-df21965892b7","name":"Mirror Of A Generic Tree","type":3,"slug":"mirror-of-a-generic-tree"},"prev":{"id":"7e50a09f-e80c-4f93-b683-dc8cfa75eff0","name":"Level Order traversals - More Approaches","type":0,"slug":"level-order-traversals-more-approaches"}}}
plane

Editor


Loading...

Mirror A Generic Tree

medium

1. You are given a partially written GenericTree class. 2. You are required to complete the body of mirror function. The function is expected to create a mirror image of the tree. For more details, check out the question video. 3. Input and Output is managed for you.

Constraints

None

Format

Input

Input is managed for you

Output

Output is managed for you

Example

Sample Input

24 10 20 50 -1 60 -1 -1 30 70 -1 80 110 -1 120 -1 -1 90 -1 -1 40 100 -1 -1 -1

Sample Output

10 -> 20, 30, 40, . 20 -> 50, 60, . 50 -> . 60 -> . 30 -> 70, 80, 90, . 70 -> . 80 -> 110, 120, . 110 -> . 120 -> . 90 -> . 40 -> 100, . 100 -> . 10 -> 40, 30, 20, . 40 -> 100, . 100 -> . 30 -> 90, 80, 70, . 90 -> . 80 -> 120, 110, . 120 -> . 110 -> . 70 -> . 20 -> 60, 50, . 60 -> . 50 -> .

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode