{"id":"d36584f1-0d85-486e-bea0-7ef1d7fb9b04","name":"Are Trees Similar In Shape","description":"1. You are given a partially written GenericTree class.\r\n2. You are required to complete the body of areSimilar function. The function is expected to check if the two trees passed to it are similar in shape or not.\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":"#include<bits/stdc++.h>\n#include<climits>\n\nusing namespace std;\n\nclass Node\n{\npublic:\n int data = 0;\n vector<Node *> children;\n\n Node(int data)\n {\n this->data = data;\n }\n};\n\n\nvoid display(Node *node)\n{\n string s = \"\";\n s += to_string(node->data) + \" Child: \";\n for (Node *child : node->children)\n {\n s += to_string(child->data) + \", \";\n }\n\n cout << s << \".\" << endl;\n\n for (Node *child : node->children)\n {\n display(child);\n }\n}\n\nNode *constructor01(vector<int>arr)\n{\n if (arr.size() == 0)\n return NULL;\n\n vector<Node *> stack;\n stack.push_back(new Node(arr[0]));\n\n Node *root = stack[0];\n\n for (int i = 1; i < arr.size(); i++)\n {\n if (arr[i] != -1)\n {\n Node *node = stack.back();\n Node *nnode = new Node(arr[i]);\n\n node->children.push_back(nnode);\n stack.push_back(nnode);\n }\n else\n stack.pop_back();\n }\n return root;\n}\n\n\nint sizeRec(Node *node)\n{\n int size = 0;\n for (Node *child : node->children)\n {\n size += sizeRec(child);\n }\n return size + 1;\n}\n\n\nint maxEle(Node *node)\n{\n int OverMax = node->data;\n for (Node *child : node->children)\n {\n OverMax = max(OverMax, maxEle(child));\n }\n return OverMax;\n}\n\n\nint height(Node *node)\n{\n int ht = 0;\n for (Node *child : node->children)\n {\n ht = max(ht, height(child));\n }\n return ht + 1;\n}\n\n\nbool areSimilar(Node *n1, Node *n2) \n{\n \n // Write your code here\n}\n\n\nvoid solve()\n{\n int n1;\n cin>>n1;\n vector<int>arr1(n1,0);\n for(int i = 0; i < n1; i++)\n {\n cin>>arr1[i];\n }\n Node *root1 = constructor01(arr1);\n \n int n2;\n cin>>n2;\n vector<int>arr2(n2,0);\n for(int i = 0; i < n2; i++)\n {\n cin>>arr2[i];\n }\n \n Node *root2 = constructor01(arr2);\n \n bool similar = areSimilar(root1, root2);\n if(similar == true)\n {\n cout<<\"true\"<<endl;\n }\n else\n {\n cout<<\"false\"<<endl;\n }\n}\n\nint main()\n{\n solve();\n return 0;\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 boolean areSimilar(Node n1, Node n2) {\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\r\n int n1 = Integer.parseInt(br.readLine());\r\n int[] arr1 = new int[n1];\r\n String[] values1 = br.readLine().split(\" \");\r\n for (int i = 0; i < n1; i++) {\r\n arr1[i] = Integer.parseInt(values1[i]);\r\n }\r\n Node root1 = construct(arr1);\r\n\r\n int n2 = Integer.parseInt(br.readLine());\r\n int[] arr2 = new int[n2];\r\n String[] values2 = br.readLine().split(\" \");\r\n for (int i = 0; i < n2; i++) {\r\n arr2[i] = Integer.parseInt(values2[i]);\r\n }\r\n Node root2 = construct(arr2);\r\n\r\n boolean similar = areSimilar(root1, root2);\r\n System.out.println(similar);\r\n }\r\n\r\n}"},"python":{"code":"class Node:\n def __init__(self, data):\n self.data = data\n self.children = []\n\n# create a new tree node\n\ndef newNode(data):\n temp = Node(data)\n return temp \n\n\n# n-ary tree level wise\n\ndef constructor(lst, n):\n root = None\n stack = []\n for i in range(0, n) :\n if lst[i] == -1:\n stack.pop()\n else:\n t = Node(lst[i])\n if len(stack) > 0:\n stack[-1].children.append(t)\n\n else:\n root = t\n\n stack.append(t)\n\n return root\n\n\ndef areSimilar(root1, root2):\n \n \n # Write your code here\n \n \n\n# main function\n\nif __name__ == \"__main__\":\n \n lst1 = [] \n n1 = int(input())\n lst1 = list(map(int, input().split(\" \")))\n root1 = constructor(lst1, n1)\n \n \n lst2 = [] \n n2 = int(input())\n lst2 = list(map(int, input().split(\" \")))\n root2 = constructor(lst2, n2)\n\n\n flag = areSimilar(root1,root2)\n if flag == False:\n print(\"false\")\n \n else:\n print(\"true\")"}},"points":10,"difficulty":"easy","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\r\n24\r\n1 2 5 -1 6 -1 -1 3 7 -1 8 11 -1 12 -1 -1 9 -1 -1 4 10 -1 -1 -1","sampleOutput":"true","questionVideo":"https://www.youtube.com/embed/rumfdyFR-_A","hints":[],"associated":[{"id":"7cba6df4-d4c5-492c-ba87-d6610c621a55","name":"Checking only root node child is sufficient for checking are trees similar in shape?","slug":"checking-only-root-node-child-is-sufficient-for-checking-are-trees-similar-in-shape","type":4},{"id":"c3d2e45e-c042-4532-91f6-adc3c3826332","name":"What is your first step for checking are trees similar or not??","slug":"what-is-your-first-step-for-checking-are-trees-similar-or-not","type":4},{"id":"d5360790-00a6-46b8-8bd7-e0c7f60de0ac","name":"What is our high-level thing for this question?","slug":"what-is-our-high-level-thing-for-this-question","type":4},{"id":"f7699806-b563-43c6-9f74-d18193c0b00e","name":"If the leaf nodes of both trees are not the same then are similar they or not?","slug":"if-the-leaf-nodes-of-both-trees-are-not-the-same-then-are-similar-they-or-not","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":"2bf65642-0641-4ffd-ace7-c36588a71474","name":"Are Trees Similar In Shape","slug":"are-trees-similar-in-shape","type":1}],"next":{"id":"5d698373-59e6-439c-8cb7-b7f45476edc8","name":"Are Trees Similar In Shape","type":3,"slug":"are-trees-similar-in-shape"},"prev":{"id":"50c4f981-2356-446d-af31-99af683b1d42","name":"Distance Between Two Nodes In A Generic Tree","type":3,"slug":"distance-between-two-nodes-in-a-generic-tree"}}}

Are Trees Similar In Shape

1. You are given a partially written GenericTree class. 2. You are required to complete the body of areSimilar function. The function is expected to check if the two trees passed to it are similar in shape or not. 3. Input and Output is managed for you.

{"id":"d36584f1-0d85-486e-bea0-7ef1d7fb9b04","name":"Are Trees Similar In Shape","description":"1. You are given a partially written GenericTree class.\r\n2. You are required to complete the body of areSimilar function. The function is expected to check if the two trees passed to it are similar in shape or not.\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":"#include<bits/stdc++.h>\n#include<climits>\n\nusing namespace std;\n\nclass Node\n{\npublic:\n int data = 0;\n vector<Node *> children;\n\n Node(int data)\n {\n this->data = data;\n }\n};\n\n\nvoid display(Node *node)\n{\n string s = \"\";\n s += to_string(node->data) + \" Child: \";\n for (Node *child : node->children)\n {\n s += to_string(child->data) + \", \";\n }\n\n cout << s << \".\" << endl;\n\n for (Node *child : node->children)\n {\n display(child);\n }\n}\n\nNode *constructor01(vector<int>arr)\n{\n if (arr.size() == 0)\n return NULL;\n\n vector<Node *> stack;\n stack.push_back(new Node(arr[0]));\n\n Node *root = stack[0];\n\n for (int i = 1; i < arr.size(); i++)\n {\n if (arr[i] != -1)\n {\n Node *node = stack.back();\n Node *nnode = new Node(arr[i]);\n\n node->children.push_back(nnode);\n stack.push_back(nnode);\n }\n else\n stack.pop_back();\n }\n return root;\n}\n\n\nint sizeRec(Node *node)\n{\n int size = 0;\n for (Node *child : node->children)\n {\n size += sizeRec(child);\n }\n return size + 1;\n}\n\n\nint maxEle(Node *node)\n{\n int OverMax = node->data;\n for (Node *child : node->children)\n {\n OverMax = max(OverMax, maxEle(child));\n }\n return OverMax;\n}\n\n\nint height(Node *node)\n{\n int ht = 0;\n for (Node *child : node->children)\n {\n ht = max(ht, height(child));\n }\n return ht + 1;\n}\n\n\nbool areSimilar(Node *n1, Node *n2) \n{\n \n // Write your code here\n}\n\n\nvoid solve()\n{\n int n1;\n cin>>n1;\n vector<int>arr1(n1,0);\n for(int i = 0; i < n1; i++)\n {\n cin>>arr1[i];\n }\n Node *root1 = constructor01(arr1);\n \n int n2;\n cin>>n2;\n vector<int>arr2(n2,0);\n for(int i = 0; i < n2; i++)\n {\n cin>>arr2[i];\n }\n \n Node *root2 = constructor01(arr2);\n \n bool similar = areSimilar(root1, root2);\n if(similar == true)\n {\n cout<<\"true\"<<endl;\n }\n else\n {\n cout<<\"false\"<<endl;\n }\n}\n\nint main()\n{\n solve();\n return 0;\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 boolean areSimilar(Node n1, Node n2) {\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\r\n int n1 = Integer.parseInt(br.readLine());\r\n int[] arr1 = new int[n1];\r\n String[] values1 = br.readLine().split(\" \");\r\n for (int i = 0; i < n1; i++) {\r\n arr1[i] = Integer.parseInt(values1[i]);\r\n }\r\n Node root1 = construct(arr1);\r\n\r\n int n2 = Integer.parseInt(br.readLine());\r\n int[] arr2 = new int[n2];\r\n String[] values2 = br.readLine().split(\" \");\r\n for (int i = 0; i < n2; i++) {\r\n arr2[i] = Integer.parseInt(values2[i]);\r\n }\r\n Node root2 = construct(arr2);\r\n\r\n boolean similar = areSimilar(root1, root2);\r\n System.out.println(similar);\r\n }\r\n\r\n}"},"python":{"code":"class Node:\n def __init__(self, data):\n self.data = data\n self.children = []\n\n# create a new tree node\n\ndef newNode(data):\n temp = Node(data)\n return temp \n\n\n# n-ary tree level wise\n\ndef constructor(lst, n):\n root = None\n stack = []\n for i in range(0, n) :\n if lst[i] == -1:\n stack.pop()\n else:\n t = Node(lst[i])\n if len(stack) > 0:\n stack[-1].children.append(t)\n\n else:\n root = t\n\n stack.append(t)\n\n return root\n\n\ndef areSimilar(root1, root2):\n \n \n # Write your code here\n \n \n\n# main function\n\nif __name__ == \"__main__\":\n \n lst1 = [] \n n1 = int(input())\n lst1 = list(map(int, input().split(\" \")))\n root1 = constructor(lst1, n1)\n \n \n lst2 = [] \n n2 = int(input())\n lst2 = list(map(int, input().split(\" \")))\n root2 = constructor(lst2, n2)\n\n\n flag = areSimilar(root1,root2)\n if flag == False:\n print(\"false\")\n \n else:\n print(\"true\")"}},"points":10,"difficulty":"easy","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\r\n24\r\n1 2 5 -1 6 -1 -1 3 7 -1 8 11 -1 12 -1 -1 9 -1 -1 4 10 -1 -1 -1","sampleOutput":"true","questionVideo":"https://www.youtube.com/embed/rumfdyFR-_A","hints":[],"associated":[{"id":"7cba6df4-d4c5-492c-ba87-d6610c621a55","name":"Checking only root node child is sufficient for checking are trees similar in shape?","slug":"checking-only-root-node-child-is-sufficient-for-checking-are-trees-similar-in-shape","type":4},{"id":"c3d2e45e-c042-4532-91f6-adc3c3826332","name":"What is your first step for checking are trees similar or not??","slug":"what-is-your-first-step-for-checking-are-trees-similar-or-not","type":4},{"id":"d5360790-00a6-46b8-8bd7-e0c7f60de0ac","name":"What is our high-level thing for this question?","slug":"what-is-our-high-level-thing-for-this-question","type":4},{"id":"f7699806-b563-43c6-9f74-d18193c0b00e","name":"If the leaf nodes of both trees are not the same then are similar they or not?","slug":"if-the-leaf-nodes-of-both-trees-are-not-the-same-then-are-similar-they-or-not","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":"2bf65642-0641-4ffd-ace7-c36588a71474","name":"Are Trees Similar In Shape","slug":"are-trees-similar-in-shape","type":1}],"next":{"id":"5d698373-59e6-439c-8cb7-b7f45476edc8","name":"Are Trees Similar In Shape","type":3,"slug":"are-trees-similar-in-shape"},"prev":{"id":"50c4f981-2356-446d-af31-99af683b1d42","name":"Distance Between Two Nodes In A Generic Tree","type":3,"slug":"distance-between-two-nodes-in-a-generic-tree"}}}
plane

Editor

Loading...

Are Trees Similar In Shape

easy

1. You are given a partially written GenericTree class. 2. You are required to complete the body of areSimilar function. The function is expected to check if the two trees passed to it are similar in shape or not. 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 24 1 2 5 -1 6 -1 -1 3 7 -1 8 11 -1 12 -1 -1 9 -1 -1 4 10 -1 -1 -1

Sample Output

true

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode