{"id":"982b20f9-c00c-4824-b8cf-36d704a1705e","name":"Diameter Of Generic Tree","description":"1. You are given a partially written GenericTree class.\r\n2. You are required to find and print the diameter of tree. THe diameter is defined as maximum number of edges between any two nodes in the tree. Check the question video for clarity.\r\n3. Input is managed for you.","inputFormat":"Input is managed for you","outputFormat":"diameter","constraints":"None","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nclass Node {\n public:\n int data;\n vector<Node*>children;\n};\n\n\n\nNode* construct(vector<int>&arr) {\n Node* root = nullptr;\n\n stack <Node*> st;\n for (int i = 0; i < arr.size(); i++) {\n if (arr[i] == -1) {\n st.pop();\n } else {\n Node* t = new Node();\n t->data = arr[i];\n\n if (st.size() > 0) {\n st.top()->children.push_back(t);\n } else {\n root = t;\n }\n st.push(t);\n }\n }\n return root;\n }\nint dia = 0;\n int diameter(Node* root){ \n//write your code here\n}\nint main(){\n int n,x;\n cin>>n;\n vector<int>arr;\n for(int i=0;i<n;i++){\n cin>>x;\n arr.push_back(x);\n }\n Node *root = construct(arr);\n dia=0;\n diameter(root);\n cout<<dia<<endl;\n \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 \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 // write your code here\r\n }\r\n\r\n}"},"python":{"code":"import math\nclass Node:\n def __init__(self, key):\n self.data=key\n self.child=[]\n \ndef newNode(key):\n temp= Node(key)\n return temp\n \nclass Pair:\n def __init__(self,node,st):\n self.node=node;\n self.state=st\n\ndef construct(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].child.append(t)\n else:\n root=t\n stack.append(t)\n return root\n \ndia=0;\ndef diameter(node):\n \n#write your code here\n \n \nn=int(input())\nvalues = list(map(str, input().split()))\narr=[0]*n\nfor i in range(0,n):\n if values[i]!=\"n\":\n arr[i]=int(values[i])\n else:\n arr[i]=None\nroot=construct(arr,n)\ndiameter(root)\nprint(dia)"}},"points":10,"difficulty":"medium","sampleInput":"20\r\n10 20 -50 -1 60 -1 -1 30 -70 -1 80 -1 90 -1 -1 40 -100 -1 -1 -1","sampleOutput":"4","questionVideo":"https://www.youtube.com/embed/_LVi8UWDCh8","hints":[],"associated":[{"id":"7ac859fa-8a9f-4f0c-a807-6e21503f5fd1","name":"How to calculate the 2 highest child heights of a node, max height to be stored in h1, 2nd max height to be stored in h2?","slug":"how-to-calculate-the-2-highest-child-heights-of-a-node-max-height-to-be-stored-in-h1-2nd-max-height-to-be-stored-in-h2","type":4},{"id":"7aea71a9-2702-432a-abaa-da9cba551950","name":"Updation of the answer is being done in preorder. True or false?","slug":"updation-of-the-answer-is-being-done-in-preorder-true-or-false","type":4},{"id":"7b520eca-1014-4842-b0b6-7a8ce55b41c4","name":"What is the space complexity of \"Diameter Of Generic Tree\"?","slug":"what-is-the-space-complexity-of-diameter-of-generic-tree","type":4},{"id":"a5306259-0972-42c3-a623-9c06cb319301","name":"Given 2 maximum child heights,h1 and h2, what is formula for calculating the diameter of the node?","slug":"given-2-maximum-child-heights-h1-and-h2-what-is-formula-for-calculating-the-diameter-of-the-node","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":"c288da49-199d-4f21-a316-ec07c25b8816","name":"Diameter Of Generic Tree","slug":"diameter-of-generic-tree","type":1}],"next":{"id":"6ef720df-f5c2-47a4-9720-d623dbdcb6c4","name":"Diameter in a Generic Tree","type":3,"slug":"diameter-in-a-generic-tree"},"prev":{"id":"90e258dc-5c9d-4698-893f-5d9d6521d896","name":"Node with Maximum Subtree Sum:","type":3,"slug":"node-with-maximum-subtree-sum"}}}1. You are given a partially written GenericTree class. 2. You are required to find and print the diameter of tree. THe diameter is defined as maximum number of edges between any two nodes in the tree. Check the question video for clarity. 3. Input is managed for you.
{"id":"982b20f9-c00c-4824-b8cf-36d704a1705e","name":"Diameter Of Generic Tree","description":"1. You are given a partially written GenericTree class.\r\n2. You are required to find and print the diameter of tree. THe diameter is defined as maximum number of edges between any two nodes in the tree. Check the question video for clarity.\r\n3. Input is managed for you.","inputFormat":"Input is managed for you","outputFormat":"diameter","constraints":"None","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nclass Node {\n public:\n int data;\n vector<Node*>children;\n};\n\n\n\nNode* construct(vector<int>&arr) {\n Node* root = nullptr;\n\n stack <Node*> st;\n for (int i = 0; i < arr.size(); i++) {\n if (arr[i] == -1) {\n st.pop();\n } else {\n Node* t = new Node();\n t->data = arr[i];\n\n if (st.size() > 0) {\n st.top()->children.push_back(t);\n } else {\n root = t;\n }\n st.push(t);\n }\n }\n return root;\n }\nint dia = 0;\n int diameter(Node* root){ \n//write your code here\n}\nint main(){\n int n,x;\n cin>>n;\n vector<int>arr;\n for(int i=0;i<n;i++){\n cin>>x;\n arr.push_back(x);\n }\n Node *root = construct(arr);\n dia=0;\n diameter(root);\n cout<<dia<<endl;\n \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 \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 // write your code here\r\n }\r\n\r\n}"},"python":{"code":"import math\nclass Node:\n def __init__(self, key):\n self.data=key\n self.child=[]\n \ndef newNode(key):\n temp= Node(key)\n return temp\n \nclass Pair:\n def __init__(self,node,st):\n self.node=node;\n self.state=st\n\ndef construct(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].child.append(t)\n else:\n root=t\n stack.append(t)\n return root\n \ndia=0;\ndef diameter(node):\n \n#write your code here\n \n \nn=int(input())\nvalues = list(map(str, input().split()))\narr=[0]*n\nfor i in range(0,n):\n if values[i]!=\"n\":\n arr[i]=int(values[i])\n else:\n arr[i]=None\nroot=construct(arr,n)\ndiameter(root)\nprint(dia)"}},"points":10,"difficulty":"medium","sampleInput":"20\r\n10 20 -50 -1 60 -1 -1 30 -70 -1 80 -1 90 -1 -1 40 -100 -1 -1 -1","sampleOutput":"4","questionVideo":"https://www.youtube.com/embed/_LVi8UWDCh8","hints":[],"associated":[{"id":"7ac859fa-8a9f-4f0c-a807-6e21503f5fd1","name":"How to calculate the 2 highest child heights of a node, max height to be stored in h1, 2nd max height to be stored in h2?","slug":"how-to-calculate-the-2-highest-child-heights-of-a-node-max-height-to-be-stored-in-h1-2nd-max-height-to-be-stored-in-h2","type":4},{"id":"7aea71a9-2702-432a-abaa-da9cba551950","name":"Updation of the answer is being done in preorder. True or false?","slug":"updation-of-the-answer-is-being-done-in-preorder-true-or-false","type":4},{"id":"7b520eca-1014-4842-b0b6-7a8ce55b41c4","name":"What is the space complexity of \"Diameter Of Generic Tree\"?","slug":"what-is-the-space-complexity-of-diameter-of-generic-tree","type":4},{"id":"a5306259-0972-42c3-a623-9c06cb319301","name":"Given 2 maximum child heights,h1 and h2, what is formula for calculating the diameter of the node?","slug":"given-2-maximum-child-heights-h1-and-h2-what-is-formula-for-calculating-the-diameter-of-the-node","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":"c288da49-199d-4f21-a316-ec07c25b8816","name":"Diameter Of Generic Tree","slug":"diameter-of-generic-tree","type":1}],"next":{"id":"6ef720df-f5c2-47a4-9720-d623dbdcb6c4","name":"Diameter in a Generic Tree","type":3,"slug":"diameter-in-a-generic-tree"},"prev":{"id":"90e258dc-5c9d-4698-893f-5d9d6521d896","name":"Node with Maximum Subtree Sum:","type":3,"slug":"node-with-maximum-subtree-sum"}}}
Editor
Discussions
Show Discussion
Related Resources
