`{"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"}}}` Editor

# 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.

None

## Format

### Input

Input is managed for you

### Output

Output is managed for you

## Example

Sample Input

```.css-23h8hz{color:inherit;font-size:0.875rem;line-height:1.125rem;letter-spacing:0.016rem;font-weight:var(--chakra-fontWeights-normal);white-space:pre-wrap;}12 10 20 -1 30 50 -1 60 -1 -1 40 -1 -1```

### Sample Output

`.css-3oaykw{color:var(--chakra-colors-active-primary);font-size:0.875rem;line-height:1.125rem;letter-spacing:0.016rem;font-weight:var(--chakra-fontWeights-normal);white-space:pre-wrap;font-family:Monospace;}2`

Question Video

Discussions

Show Discussion

Related Resources 