{"id":"7e3ed077-fd4a-4bf5-b949-24d595310856","name":"Height Of A Generic Tree","description":"1. You are given a partially written GenericTree class.\r\n2. You are required to complete the body of height function. The function is expected to find the height of tree. Depth of a node is defined as the number of edges it is away from the root (depth of root is 0). Height of a tree is defined as depth of deepest node.\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>\nusing namespace std;\nstruct Node{\n int data;\n vector<Node*>children;\n};\n\nNode *newNode(int key)\n{\n\tNode *temp=new Node;\n\ttemp->data=key;\n\treturn temp;\n\n}\n\nNode *construct(int arr[],int n )\n{\n Node *root=NULL;\n stack<Node*>st;\n for(int i=0;i<n;i++){\n if(arr[i]==-1){\n st.pop();\n }else{\n Node *t=newNode(arr[i]);\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}\n\nint height(Node *node)\n{\n //Write your code here\n}\n\nint main()\n{\n int n;\n cin>>n;\n int arr[n];\n for(int i=0;i<n;i++)\n {\n cin>>arr[i];\n }\n Node *root=construct(arr,n);\n int h=height(root);\n cout << h << endl;\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 // 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 int h = height(root);\r\n System.out.println(h);\r\n // display(root);\r\n }\r\n\r\n}"},"python":{"code":"import math\nclass Node:\n \n def __init__(self, key):\n \n self.key = key\n self.child = []\n\ndef newNode(key): \n temp = Node(key)\n return temp\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].child.append(t)\n \n else:\n root=t\n \n stack.append(t)\n return root\n \ndef height(root):\n #write your code here\n \nlst = []\nn = int(input())\nlst = list(map(int, input().split()))\nroot = constructor(lst,n) \nprint(height(root))"}},"points":10,"difficulty":"easy","sampleInput":"12\r\n10 20 -1 30 50 -1 60 -1 -1 40 -1 -1","sampleOutput":"2","questionVideo":"https://www.youtube.com/embed/Vm5ubT7aPmI","hints":[],"associated":[{"id":"60b613a8-b351-4861-800b-98f1a27c3c62","name":"What is going to be the time complexity of our solution of \"Height Of A Generic Tree\"?","slug":"what-is-going-to-be-the-time-complexity-of-our-solution-of-height-of-a-generic-tree","type":4},{"id":"91e14a75-e16a-44c3-ad5a-61f063c7dca3","name":"We will initialize height variable with what?","slug":"we-will-initialize-height-variable-with-what","type":4},{"id":"947e875c-1a10-4ec5-be8d-e4586fa13d79","name":"What is going to be the Space complexity of our solution \"Height Of A Generic Tree\"?","slug":"what-is-going-to-be-the-space-complexity-of-our-solution-height-of-a-generic-tree","type":4},{"id":"dc25141f-87d6-4101-883e-23b0f150bf57","name":"Height in our question is defined in terms of what?","slug":"height-in-our-question-is-defined-in-terms-of-what","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":"d73af575-2e84-49ca-b306-1b893ab9cc8e","name":"Height Of A Generic Tree","slug":"height-of-a-generic-tree","type":1}],"next":{"id":"0c9f3712-613c-4eb8-8912-5310fd56ec22","name":"Height of a Generic Tree","type":3,"slug":"height-of-a-generic-tree"},"prev":{"id":"73893be1-d1a8-4ca1-bef5-62976b607161","name":"Maximum in a Generic Tree","type":3,"slug":"maximum-in-a-generic-tree"}}}

Height Of A Generic Tree

1. You are given a partially written GenericTree class. 2. You are required to complete the body of height function. The function is expected to find the height of tree. Depth of a node is defined as the number of edges it is away from the root (depth of root is 0). Height of a tree is defined as depth of deepest node. 3. Input and Output is managed for you.

{"id":"7e3ed077-fd4a-4bf5-b949-24d595310856","name":"Height Of A Generic Tree","description":"1. You are given a partially written GenericTree class.\r\n2. You are required to complete the body of height function. The function is expected to find the height of tree. Depth of a node is defined as the number of edges it is away from the root (depth of root is 0). Height of a tree is defined as depth of deepest node.\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>\nusing namespace std;\nstruct Node{\n int data;\n vector<Node*>children;\n};\n\nNode *newNode(int key)\n{\n\tNode *temp=new Node;\n\ttemp->data=key;\n\treturn temp;\n\n}\n\nNode *construct(int arr[],int n )\n{\n Node *root=NULL;\n stack<Node*>st;\n for(int i=0;i<n;i++){\n if(arr[i]==-1){\n st.pop();\n }else{\n Node *t=newNode(arr[i]);\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}\n\nint height(Node *node)\n{\n //Write your code here\n}\n\nint main()\n{\n int n;\n cin>>n;\n int arr[n];\n for(int i=0;i<n;i++)\n {\n cin>>arr[i];\n }\n Node *root=construct(arr,n);\n int h=height(root);\n cout << h << endl;\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 // 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 int h = height(root);\r\n System.out.println(h);\r\n // display(root);\r\n }\r\n\r\n}"},"python":{"code":"import math\nclass Node:\n \n def __init__(self, key):\n \n self.key = key\n self.child = []\n\ndef newNode(key): \n temp = Node(key)\n return temp\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].child.append(t)\n \n else:\n root=t\n \n stack.append(t)\n return root\n \ndef height(root):\n #write your code here\n \nlst = []\nn = int(input())\nlst = list(map(int, input().split()))\nroot = constructor(lst,n) \nprint(height(root))"}},"points":10,"difficulty":"easy","sampleInput":"12\r\n10 20 -1 30 50 -1 60 -1 -1 40 -1 -1","sampleOutput":"2","questionVideo":"https://www.youtube.com/embed/Vm5ubT7aPmI","hints":[],"associated":[{"id":"60b613a8-b351-4861-800b-98f1a27c3c62","name":"What is going to be the time complexity of our solution of \"Height Of A Generic Tree\"?","slug":"what-is-going-to-be-the-time-complexity-of-our-solution-of-height-of-a-generic-tree","type":4},{"id":"91e14a75-e16a-44c3-ad5a-61f063c7dca3","name":"We will initialize height variable with what?","slug":"we-will-initialize-height-variable-with-what","type":4},{"id":"947e875c-1a10-4ec5-be8d-e4586fa13d79","name":"What is going to be the Space complexity of our solution \"Height Of A Generic Tree\"?","slug":"what-is-going-to-be-the-space-complexity-of-our-solution-height-of-a-generic-tree","type":4},{"id":"dc25141f-87d6-4101-883e-23b0f150bf57","name":"Height in our question is defined in terms of what?","slug":"height-in-our-question-is-defined-in-terms-of-what","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":"d73af575-2e84-49ca-b306-1b893ab9cc8e","name":"Height Of A Generic Tree","slug":"height-of-a-generic-tree","type":1}],"next":{"id":"0c9f3712-613c-4eb8-8912-5310fd56ec22","name":"Height of a Generic Tree","type":3,"slug":"height-of-a-generic-tree"},"prev":{"id":"73893be1-d1a8-4ca1-bef5-62976b607161","name":"Maximum in a Generic Tree","type":3,"slug":"maximum-in-a-generic-tree"}}}
plane

Editor

Loading...

Height Of A Generic Tree

easy

1. You are given a partially written GenericTree class. 2. You are required to complete the body of height function. The function is expected to find the height of tree. Depth of a node is defined as the number of edges it is away from the root (depth of root is 0). Height of a tree is defined as depth of deepest node. 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

12 10 20 -1 30 50 -1 60 -1 -1 40 -1 -1

Sample Output

2

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode