{"id":"7cf66f50-77b4-44c5-9529-d63ab91b2d4d","name":"Size Of Generic Tree","description":"1. You are given a partially written GenericTree class.\r\n2. You are required to complete the body of size function. The function is expected to count the number of nodes in the tree and return it.\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\tNode *temp=new Node;\n\ttemp->data=key;\n\treturn temp;\n\n}\n\nNode *construct(int arr[],int 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 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}\nvoid display(Node *node)\n{\n string str= to_string(node->data) + \"-> \";\n for(Node *child: node->children)\n {\n str+=to_string(child->data)+\", \";\n }\n str= str+\".\";\n cout << str <<endl;\n for(Node *child : node->children)\n {\n display(child);\n }\n}\n\nint size(Node *node){\n //write your code here\n}\n\nint main(){\n \n int n;\n cin>>n;\n \n int arr[n];\n for(int i=0;i<n;i++){\n cin>>arr[i];\n }\n Node *root=construct(arr,n);\n int sz=size(root);\n cout<<sz<<endl;\n //display(root);\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 // 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 sz = size(root);\r\n System.out.println(sz);\r\n // display(root);\r\n }\r\n\r\n}"},"python":{"code":"class 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 display(root):\n s= str(root.key)+\"->\"\n for x in root.child:\n s += str(x.key)+\", \"\n s += \".\" \n print(s)\n for x in root.child:\n display(x)\n \ndef size(root):\n # write your code here\n \nlst = []\nn = int(input())\nlst = list(map(int, input().split()))\nroot = constructor(lst,n)\n# display(root)\nprint(size(root))"}},"points":10,"difficulty":"medium","sampleInput":"12\r\n10 20 -1 30 50 -1 60 -1 -1 40 -1 -1","sampleOutput":"6","questionVideo":"https://www.youtube.com/embed/TLWt90wcFIM","hints":[],"associated":[{"id":"1a3ffc96-95ff-48fa-8971-040d4cc282c7","name":"What is the space complexity of the\"size of a generic tree\"?","slug":"what-is-the-space-complexity-of-the-size-of-a-generic-tree-14867","type":4},{"id":"50f1f4de-7ba9-4dd2-961b-31ecc9fb6bac","name":"What is the time complexity of \"size of generic tree\" ?","slug":"what-is-the-time-complexity-of-size-of-generic-tree","type":4},{"id":"d81a9d98-2adf-4789-975e-507f593c08d7","name":"What will be the worst-case scenario when space complexity is O(n) in \"size of Generic Tree\"?","slug":"what-will-be-the-worst-case-scenario-when-space-complexity-is-o-n-in-size-of-generic-tree","type":4},{"id":"db5b9f65-27f5-40e0-8f9c-608258628ca9","name":"What should be the base case for the recursive call?","slug":"what-should-be-the-base-case-for-the-recursive-call","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":"13935d20-cb31-4b92-941c-fc5b53bfb086","name":"Size Of Generic Tree","slug":"size-of-generic-tree","type":1}],"next":{"id":"5fb3915a-d830-4014-9a0b-8a161a0ae084","name":"Size of Generic Tree","type":3,"slug":"size-of-generic-tree"},"prev":{"id":"6063b5f6-c256-4de1-9ef3-0e6b45d62b2f","name":"Display A Generic Tree","type":0,"slug":"display-a-generic-tree"}}}1. You are given a partially written GenericTree class. 2. You are required to complete the body of size function. The function is expected to count the number of nodes in the tree and return it. 3. Input and Output is managed for you.
{"id":"7cf66f50-77b4-44c5-9529-d63ab91b2d4d","name":"Size Of Generic Tree","description":"1. You are given a partially written GenericTree class.\r\n2. You are required to complete the body of size function. The function is expected to count the number of nodes in the tree and return it.\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\tNode *temp=new Node;\n\ttemp->data=key;\n\treturn temp;\n\n}\n\nNode *construct(int arr[],int 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 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}\nvoid display(Node *node)\n{\n string str= to_string(node->data) + \"-> \";\n for(Node *child: node->children)\n {\n str+=to_string(child->data)+\", \";\n }\n str= str+\".\";\n cout << str <<endl;\n for(Node *child : node->children)\n {\n display(child);\n }\n}\n\nint size(Node *node){\n //write your code here\n}\n\nint main(){\n \n int n;\n cin>>n;\n \n int arr[n];\n for(int i=0;i<n;i++){\n cin>>arr[i];\n }\n Node *root=construct(arr,n);\n int sz=size(root);\n cout<<sz<<endl;\n //display(root);\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 // 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 sz = size(root);\r\n System.out.println(sz);\r\n // display(root);\r\n }\r\n\r\n}"},"python":{"code":"class 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 display(root):\n s= str(root.key)+\"->\"\n for x in root.child:\n s += str(x.key)+\", \"\n s += \".\" \n print(s)\n for x in root.child:\n display(x)\n \ndef size(root):\n # write your code here\n \nlst = []\nn = int(input())\nlst = list(map(int, input().split()))\nroot = constructor(lst,n)\n# display(root)\nprint(size(root))"}},"points":10,"difficulty":"medium","sampleInput":"12\r\n10 20 -1 30 50 -1 60 -1 -1 40 -1 -1","sampleOutput":"6","questionVideo":"https://www.youtube.com/embed/TLWt90wcFIM","hints":[],"associated":[{"id":"1a3ffc96-95ff-48fa-8971-040d4cc282c7","name":"What is the space complexity of the\"size of a generic tree\"?","slug":"what-is-the-space-complexity-of-the-size-of-a-generic-tree-14867","type":4},{"id":"50f1f4de-7ba9-4dd2-961b-31ecc9fb6bac","name":"What is the time complexity of \"size of generic tree\" ?","slug":"what-is-the-time-complexity-of-size-of-generic-tree","type":4},{"id":"d81a9d98-2adf-4789-975e-507f593c08d7","name":"What will be the worst-case scenario when space complexity is O(n) in \"size of Generic Tree\"?","slug":"what-will-be-the-worst-case-scenario-when-space-complexity-is-o-n-in-size-of-generic-tree","type":4},{"id":"db5b9f65-27f5-40e0-8f9c-608258628ca9","name":"What should be the base case for the recursive call?","slug":"what-should-be-the-base-case-for-the-recursive-call","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":"13935d20-cb31-4b92-941c-fc5b53bfb086","name":"Size Of Generic Tree","slug":"size-of-generic-tree","type":1}],"next":{"id":"5fb3915a-d830-4014-9a0b-8a161a0ae084","name":"Size of Generic Tree","type":3,"slug":"size-of-generic-tree"},"prev":{"id":"6063b5f6-c256-4de1-9ef3-0e6b45d62b2f","name":"Display A Generic Tree","type":0,"slug":"display-a-generic-tree"}}}
Editor
Discussions
Show Discussion
Related Resources
