{"id":"9df265bd-3b5a-4a18-b9ad-b4d0411e91e8","name":"Size, Sum, Maximum And Height Of A Binary Tree","description":"1. You are given a partially written BinaryTree class.\r\n2. You are required to complete the body of size, sum, max and height function. The functions are expected to\r\n 2.1. size - return the number of nodes in BinaryTree\r\n 2.2. sum - return the sum of nodes in BinaryTree\r\n 2.3. max - return the highest node in BinaryTree\r\n 2.4. height - return the height of tree in terms of edges\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<iostream>\n#include<climits>\n#include<string.h>\n#include<vector>\n\nusing namespace std;\n\n// structure of node\nclass Node\n{\npublic:\n int data;\n Node *left = nullptr;\n Node *right = nullptr;\n Node(int data)\n {\n this->data = data;\n }\n};\n\nclass Pair {\n public:\n Node * node = nullptr;\n int state=0;\n\n Pair(Node *node, int state) {\n this->node = node;\n this->state = state;\n }\n };\n\nint idx = 0;\nNode *constructTree(vector<int> &arr)\n{\n\n if (idx == arr.size() || arr[idx] == -1)\n {\n idx++;\n return nullptr;\n }\n Node *node = new Node(arr[idx++]);\n node->left = constructTree(arr);\n node->right = constructTree(arr);\n return node;\n}\n\nvoid display(Node *node)\n{\n if (node == nullptr)\n return;\n string str = \"\";\n str += node->left != nullptr ? to_string(node->left->data) : \".\";\n str += \" <- \" + to_string(node->data) + \" -> \";\n str += node->right != nullptr ? to_string(node->right->data) : \".\";\n cout << str << endl;\n\n display(node->left);\n display(node->right);\n}\n\n\nint size(Node *node)\n{\n //write your code here\n}\n\nint height(Node *node)\n{\n //write your code here\n}\n\nint maximum(Node *node)\n{\n //write your code here\n}\n\nint sum(Node *root)\n{\n \n //write your code here\n}\n\nint main()\n{\n \n int n;\n cin>>n;\n \n vector<int> arr(n,0);\n for(int i = 0; i < n; i++){\n string temp;\n cin>>temp;\n \n if(temp==\"n\")\n {\n arr[i] = -1; \n }\n else\n {\n arr[i] = stoi(temp); \n }\n }\n \n Node *root = constructTree(arr);\n\n int sz = size(root);\n int sm = sum(root);\n int max = maximum(root);\n int ht = height(root);\n cout<<sz<<endl;\n cout<<sm<<endl;\n cout<<max<<endl;\n cout<<ht<<endl;\n }"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n public static class Node {\r\n int data;\r\n Node left;\r\n Node right;\r\n\r\n Node(int data, Node left, Node right) {\r\n this.data = data;\r\n this.left = left;\r\n this.right = right;\r\n }\r\n }\r\n\r\n public static class Pair {\r\n Node node;\r\n int state;\r\n\r\n Pair(Node node, int state) {\r\n this.node = node;\r\n this.state = state;\r\n }\r\n }\r\n\r\n public static Node construct(Integer[] arr) {\r\n Node root = new Node(arr[0], null, null);\r\n Pair rtp = new Pair(root, 1);\r\n\r\n Stack<Pair> st = new Stack<>();\r\n st.push(rtp);\r\n\r\n int idx = 0;\r\n while (st.size() > 0) {\r\n Pair top = st.peek();\r\n if (top.state == 1) {\r\n idx++;\r\n if (arr[idx] != null) {\r\n top.node.left = new Node(arr[idx], null, null);\r\n Pair lp = new Pair(top.node.left, 1);\r\n st.push(lp);\r\n } else {\r\n top.node.left = null;\r\n }\r\n\r\n top.state++;\r\n } else if (top.state == 2) {\r\n idx++;\r\n if (arr[idx] != null) {\r\n top.node.right = new Node(arr[idx], null, null);\r\n Pair rp = new Pair(top.node.right, 1);\r\n st.push(rp);\r\n } else {\r\n top.node.right = null;\r\n }\r\n\r\n top.state++;\r\n } else {\r\n st.pop();\r\n }\r\n }\r\n\r\n return root;\r\n }\r\n\r\n public static void display(Node node) {\r\n if (node == null) {\r\n return;\r\n }\r\n\r\n String str = \"\";\r\n str += node.left == null ? \".\" : node.left.data + \"\";\r\n str += \" <- \" + node.data + \" -> \";\r\n str += node.right == null ? \".\" : node.right.data + \"\";\r\n System.out.println(str);\r\n\r\n display(node.left);\r\n display(node.right);\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 int sum(Node node) {\r\n // write your code here\r\n }\r\n\r\n public static int max(Node node) {\r\n // write your code here\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 Integer[] arr = new Integer[n];\r\n String[] values = br.readLine().split(\" \");\r\n for (int i = 0; i < n; i++) {\r\n if (values[i].equals(\"n\") == false) {\r\n arr[i] = Integer.parseInt(values[i]);\r\n } else {\r\n arr[i] = null;\r\n }\r\n }\r\n\r\n Node root = construct(arr);\r\n\r\n int size = size(root);\r\n int sum = sum(root);\r\n int max = max(root);\r\n int ht = height(root);\r\n System.out.println(size);\r\n System.out.println(sum);\r\n System.out.println(max);\r\n System.out.println(ht);\r\n }\r\n\r\n}"},"python":{"code":"class Node:\n def __init__(self,data,left,right):\n self.data = data\n self.left = None\n self.right = None\nclass Pair:\n def __init__(self,node,state):\n self.node = node\n self.state = state\n\ndef construct(arr):\n root=Node(arr[0],None,None)\n rtp=Pair(root,1);\n \n st=[]\n st.append(rtp);\n \n idx=0;\n n = len(arr)\n while(len(st)>0):\n top=st[-1];\n if top.state==1:\n idx+=1\n st[-1].state+=1\n if(arr[idx]!=-1):\n top.node.left = Node(arr[idx], None, None);\n lp = Pair(top.node.left, 1);\n st.append(lp);\n else:\n top.node.left=None;\n elif top.state==2:\n idx+=1\n st[-1].state+=1\n if(arr[idx]!=-1):\n top.node.right = Node(arr[idx], None, None);\n rp = Pair(top.node.right, 1);\n st.append(rp);\n else:\n top.node.right=None;\n else:\n st.pop()\n return root;\n\n\n \ndef size(node):\n # Write your code here\n \ndef add(node):\n # Write your code here\n \ndef maximum(node):\n # Write your code here\n \ndef height(node):\n # Write your code here\n\nn = int(input())\nst = input()\narr = list(map(int,st.replace(\"n\",\"-1\").split(\" \")));\nroot = construct(arr)\nprint(size(root))\nprint(add(root))\nprint(maximum(root))\nprint(height(root))"}},"points":10,"difficulty":"easy","sampleInput":"19\r\n50 25 12 n n 37 30 n n n 75 62 n 70 n n 87 n n","sampleOutput":"9\r\n448\r\n87\r\n3","questionVideo":"https://www.youtube.com/embed/I3D3p1TG1uE","hints":[],"associated":[{"id":"05f94b1a-2baf-4763-80cd-04748da0309d","name":"What is the faith for finding the size of the Binary Tree?","slug":"what-is-the-faith-for-finding-the-size-of-the-binary-tree","type":4},{"id":"522d757e-ee59-429f-81c2-2e218bf4bed7","name":"What will be the base case for the sum() function?","slug":"what-will-be-the-base-case-for-the-sum-function","type":4},{"id":"c947cbe7-0287-4ec8-a0d3-7908dccc4eee","name":"What is the base case for finding the maximum value in a binary tree?","slug":"what-is-the-base-case-for-finding-the-maximum-value-in-a-binary-tree","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":"b042fe97-356f-41ed-80fd-abacd61fc234","name":"Binary Tree For Beginners","slug":"binary-tree-for-beginners","type":0},{"id":"66d11632-7daf-4560-8b81-2851be06260f","name":"Size, Sum, Maximum And Height Of A Binary Tree","slug":"size-sum-maximum-and-height-of-a-binary-tree","type":1}],"next":{"id":"dc6a5f19-b091-4879-985c-8d318d9545e5","name":"Size, Sum, Max and Height of a Binary Tree","type":3,"slug":"size-sum-max-and-height-of-a-binary-tree"},"prev":{"id":"81a053bc-d3f8-4ed4-be1e-db3ec2116ed3","name":"Display A Binary Tree","type":0,"slug":"display-a-binary-tree"}}}

Size, Sum, Maximum And Height Of A Binary Tree

1. You are given a partially written BinaryTree class. 2. You are required to complete the body of size, sum, max and height function. The functions are expected to 2.1. size - return the number of nodes in BinaryTree 2.2. sum - return the sum of nodes in BinaryTree 2.3. max - return the highest node in BinaryTree 2.4. height - return the height of tree in terms of edges 3. Input and Output is managed for you.

{"id":"9df265bd-3b5a-4a18-b9ad-b4d0411e91e8","name":"Size, Sum, Maximum And Height Of A Binary Tree","description":"1. You are given a partially written BinaryTree class.\r\n2. You are required to complete the body of size, sum, max and height function. The functions are expected to\r\n 2.1. size - return the number of nodes in BinaryTree\r\n 2.2. sum - return the sum of nodes in BinaryTree\r\n 2.3. max - return the highest node in BinaryTree\r\n 2.4. height - return the height of tree in terms of edges\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<iostream>\n#include<climits>\n#include<string.h>\n#include<vector>\n\nusing namespace std;\n\n// structure of node\nclass Node\n{\npublic:\n int data;\n Node *left = nullptr;\n Node *right = nullptr;\n Node(int data)\n {\n this->data = data;\n }\n};\n\nclass Pair {\n public:\n Node * node = nullptr;\n int state=0;\n\n Pair(Node *node, int state) {\n this->node = node;\n this->state = state;\n }\n };\n\nint idx = 0;\nNode *constructTree(vector<int> &arr)\n{\n\n if (idx == arr.size() || arr[idx] == -1)\n {\n idx++;\n return nullptr;\n }\n Node *node = new Node(arr[idx++]);\n node->left = constructTree(arr);\n node->right = constructTree(arr);\n return node;\n}\n\nvoid display(Node *node)\n{\n if (node == nullptr)\n return;\n string str = \"\";\n str += node->left != nullptr ? to_string(node->left->data) : \".\";\n str += \" <- \" + to_string(node->data) + \" -> \";\n str += node->right != nullptr ? to_string(node->right->data) : \".\";\n cout << str << endl;\n\n display(node->left);\n display(node->right);\n}\n\n\nint size(Node *node)\n{\n //write your code here\n}\n\nint height(Node *node)\n{\n //write your code here\n}\n\nint maximum(Node *node)\n{\n //write your code here\n}\n\nint sum(Node *root)\n{\n \n //write your code here\n}\n\nint main()\n{\n \n int n;\n cin>>n;\n \n vector<int> arr(n,0);\n for(int i = 0; i < n; i++){\n string temp;\n cin>>temp;\n \n if(temp==\"n\")\n {\n arr[i] = -1; \n }\n else\n {\n arr[i] = stoi(temp); \n }\n }\n \n Node *root = constructTree(arr);\n\n int sz = size(root);\n int sm = sum(root);\n int max = maximum(root);\n int ht = height(root);\n cout<<sz<<endl;\n cout<<sm<<endl;\n cout<<max<<endl;\n cout<<ht<<endl;\n }"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n public static class Node {\r\n int data;\r\n Node left;\r\n Node right;\r\n\r\n Node(int data, Node left, Node right) {\r\n this.data = data;\r\n this.left = left;\r\n this.right = right;\r\n }\r\n }\r\n\r\n public static class Pair {\r\n Node node;\r\n int state;\r\n\r\n Pair(Node node, int state) {\r\n this.node = node;\r\n this.state = state;\r\n }\r\n }\r\n\r\n public static Node construct(Integer[] arr) {\r\n Node root = new Node(arr[0], null, null);\r\n Pair rtp = new Pair(root, 1);\r\n\r\n Stack<Pair> st = new Stack<>();\r\n st.push(rtp);\r\n\r\n int idx = 0;\r\n while (st.size() > 0) {\r\n Pair top = st.peek();\r\n if (top.state == 1) {\r\n idx++;\r\n if (arr[idx] != null) {\r\n top.node.left = new Node(arr[idx], null, null);\r\n Pair lp = new Pair(top.node.left, 1);\r\n st.push(lp);\r\n } else {\r\n top.node.left = null;\r\n }\r\n\r\n top.state++;\r\n } else if (top.state == 2) {\r\n idx++;\r\n if (arr[idx] != null) {\r\n top.node.right = new Node(arr[idx], null, null);\r\n Pair rp = new Pair(top.node.right, 1);\r\n st.push(rp);\r\n } else {\r\n top.node.right = null;\r\n }\r\n\r\n top.state++;\r\n } else {\r\n st.pop();\r\n }\r\n }\r\n\r\n return root;\r\n }\r\n\r\n public static void display(Node node) {\r\n if (node == null) {\r\n return;\r\n }\r\n\r\n String str = \"\";\r\n str += node.left == null ? \".\" : node.left.data + \"\";\r\n str += \" <- \" + node.data + \" -> \";\r\n str += node.right == null ? \".\" : node.right.data + \"\";\r\n System.out.println(str);\r\n\r\n display(node.left);\r\n display(node.right);\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 int sum(Node node) {\r\n // write your code here\r\n }\r\n\r\n public static int max(Node node) {\r\n // write your code here\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 Integer[] arr = new Integer[n];\r\n String[] values = br.readLine().split(\" \");\r\n for (int i = 0; i < n; i++) {\r\n if (values[i].equals(\"n\") == false) {\r\n arr[i] = Integer.parseInt(values[i]);\r\n } else {\r\n arr[i] = null;\r\n }\r\n }\r\n\r\n Node root = construct(arr);\r\n\r\n int size = size(root);\r\n int sum = sum(root);\r\n int max = max(root);\r\n int ht = height(root);\r\n System.out.println(size);\r\n System.out.println(sum);\r\n System.out.println(max);\r\n System.out.println(ht);\r\n }\r\n\r\n}"},"python":{"code":"class Node:\n def __init__(self,data,left,right):\n self.data = data\n self.left = None\n self.right = None\nclass Pair:\n def __init__(self,node,state):\n self.node = node\n self.state = state\n\ndef construct(arr):\n root=Node(arr[0],None,None)\n rtp=Pair(root,1);\n \n st=[]\n st.append(rtp);\n \n idx=0;\n n = len(arr)\n while(len(st)>0):\n top=st[-1];\n if top.state==1:\n idx+=1\n st[-1].state+=1\n if(arr[idx]!=-1):\n top.node.left = Node(arr[idx], None, None);\n lp = Pair(top.node.left, 1);\n st.append(lp);\n else:\n top.node.left=None;\n elif top.state==2:\n idx+=1\n st[-1].state+=1\n if(arr[idx]!=-1):\n top.node.right = Node(arr[idx], None, None);\n rp = Pair(top.node.right, 1);\n st.append(rp);\n else:\n top.node.right=None;\n else:\n st.pop()\n return root;\n\n\n \ndef size(node):\n # Write your code here\n \ndef add(node):\n # Write your code here\n \ndef maximum(node):\n # Write your code here\n \ndef height(node):\n # Write your code here\n\nn = int(input())\nst = input()\narr = list(map(int,st.replace(\"n\",\"-1\").split(\" \")));\nroot = construct(arr)\nprint(size(root))\nprint(add(root))\nprint(maximum(root))\nprint(height(root))"}},"points":10,"difficulty":"easy","sampleInput":"19\r\n50 25 12 n n 37 30 n n n 75 62 n 70 n n 87 n n","sampleOutput":"9\r\n448\r\n87\r\n3","questionVideo":"https://www.youtube.com/embed/I3D3p1TG1uE","hints":[],"associated":[{"id":"05f94b1a-2baf-4763-80cd-04748da0309d","name":"What is the faith for finding the size of the Binary Tree?","slug":"what-is-the-faith-for-finding-the-size-of-the-binary-tree","type":4},{"id":"522d757e-ee59-429f-81c2-2e218bf4bed7","name":"What will be the base case for the sum() function?","slug":"what-will-be-the-base-case-for-the-sum-function","type":4},{"id":"c947cbe7-0287-4ec8-a0d3-7908dccc4eee","name":"What is the base case for finding the maximum value in a binary tree?","slug":"what-is-the-base-case-for-finding-the-maximum-value-in-a-binary-tree","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":"b042fe97-356f-41ed-80fd-abacd61fc234","name":"Binary Tree For Beginners","slug":"binary-tree-for-beginners","type":0},{"id":"66d11632-7daf-4560-8b81-2851be06260f","name":"Size, Sum, Maximum And Height Of A Binary Tree","slug":"size-sum-maximum-and-height-of-a-binary-tree","type":1}],"next":{"id":"dc6a5f19-b091-4879-985c-8d318d9545e5","name":"Size, Sum, Max and Height of a Binary Tree","type":3,"slug":"size-sum-max-and-height-of-a-binary-tree"},"prev":{"id":"81a053bc-d3f8-4ed4-be1e-db3ec2116ed3","name":"Display A Binary Tree","type":0,"slug":"display-a-binary-tree"}}}
plane

Editor


Loading...

Size, Sum, Maximum And Height Of A Binary Tree

easy

1. You are given a partially written BinaryTree class. 2. You are required to complete the body of size, sum, max and height function. The functions are expected to 2.1. size - return the number of nodes in BinaryTree 2.2. sum - return the sum of nodes in BinaryTree 2.3. max - return the highest node in BinaryTree 2.4. height - return the height of tree in terms of edges 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

19 50 25 12 n n 37 30 n n n 75 62 n 70 n n 87 n n

Sample Output

9 448 87 3

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode