{"id":"e6bc5a95-0c8f-4d7c-9394-e6ac865d24cd","name":"Tilt Of Binary Tree","description":"<p>1. You are given a partially written BinaryTree class. 2. You are required to complete the body of tilt function. The function is expected to set the value of data member \"tilt\". \"tilt\" of a node is the absolute value of difference between sum of nodes in it's left subtree and right subtree. \"tilt\" of the whole tree is represented as the sum of \"tilt\"s of all it's nodes. 3. Input and Output is managed for you. Note -&gt; Please refer the video for clarity.</p>","inputFormat":"Input is managed for you.","outputFormat":"Output is managed for you.","constraints":"None","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <vector>\n\nusing namespace std;\n\nclass Node\n{\npublic:\n int data=0;\n Node *left = nullptr;\n Node *right = nullptr;\n Node(int data)\n {\n this->data = data;\n }\n};\n\n class 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\n//Display function\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\n//Height function\nint height(Node *node)\n{\n return node == nullptr ? -1 : max(height(node->left), height(node->right)) + 1; // for no of edges: -1, and in terms of no of nodes return 0;\n}\n\nstatic int til = 0;\nint tilt(Node *node)\n{\n // write your code here\n}\n\nint main(){\n int n;\n cin>>n;\n \n vector<int> arr(n,0);\n for(int i = 0; i < n; i++) {\n string tmp;\n cin>>tmp;\n if (tmp==\"n\") {\n arr[i] = -1;\n } else {\n arr[i] = stoi(tmp);\n }\n }\n \n \n Node * root = constructTree(arr);\n int r = tilt(root);\n cout<<til;\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 height(Node node) {\r\n if (node == null) {\r\n return -1;\r\n }\r\n\r\n int lh = height(node.left);\r\n int rh = height(node.right);\r\n\r\n int th = Math.max(lh, rh) + 1;\r\n return th;\r\n }\r\n\r\n static int tilt = 0;\r\n public static int tilt(Node node){\r\n // write your code here to set the tilt data member\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 tilt(root);\r\n System.out.println(tilt);\r\n }\r\n\r\n}"},"python":{"code":"class Node:\n \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\ndef height(node):\n if(node == None):\n return -1\n else:\n max(height(node.left),height(node.right))+1\n return ans\n\ndef tilt(node):\n # write your code here\n \n\nn = int(input())\nst = input()\narr = [0]*n\narr = list(map(int,st.replace(\"n\",\"-1\").split(\" \")));\n\n\nroot = construct(arr)\nr = tilt(root)\nprint(Node.Tilt)"}},"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":"390","questionVideo":"https://www.youtube.com/embed/CVXfXjuBM8I","hints":[],"associated":[{"id":"4d6a1dcc-5f91-45d0-b888-e0375969830e","name":"What will be the auxiliary space complexity of \"Tilt of a Binary tree\"?","slug":"what-will-be-the-auxiliary-space-complexity-of-tilt-of-a-binary-tree","type":4},{"id":"7c193ecd-2669-4edf-8575-e9b1fc07e1b4","name":"What will be the time complexity of \"Tilt of a Binary tree\"?","slug":"what-will-be-the-time-complexity-of-tilt-of-a-binary-tree","type":4},{"id":"83aed25b-71c7-49df-b2c0-7ba5f78fd4a1","name":"Tilt of a node is the absolute value of difference between sum of nodes in it's left subtree and right subtree?","slug":"tilt-of-a-node-is-the-absolute-value-of-difference-between-sum-of-nodes-in-it-s-left-subtree-and-right-subtree","type":4},{"id":"a2d8100f-44a2-495f-a26b-b0eb9e98c9c1","name":"formula to calculate tilt of a binary tree","slug":"formula-to-calculate-tilt-of-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":"05c5235a-277a-4939-8e79-65232c71e068","name":"Tilt Of Binary Tree","slug":"tilt-of-binary-tree","type":1}],"next":{"id":"b3289da2-e27c-4fb2-8313-95716c574559","name":"Tilt of a Binary Tree","type":3,"slug":"tilt-of-a-binary-tree"},"prev":{"id":"60672207-6bbd-4fcf-bf2e-05d4dd071f63","name":"Diameter of a Binary Tree","type":3,"slug":"diameter-of-a-binary-tree"}}}

Tilt Of Binary Tree

<p>1. You are given a partially written BinaryTree class. 2. You are required to complete the body of tilt function. The function is expected to set the value of data member "tilt". "tilt" of a node is the absolute value of difference between sum of nodes in it's left subtree and right subtree. "tilt" of the whole tree is represented as the sum of "tilt"s of all it's nodes. 3. Input and Output is managed for you. Note -&gt; Please refer the video for clarity.</p>

{"id":"e6bc5a95-0c8f-4d7c-9394-e6ac865d24cd","name":"Tilt Of Binary Tree","description":"<p>1. You are given a partially written BinaryTree class. 2. You are required to complete the body of tilt function. The function is expected to set the value of data member \"tilt\". \"tilt\" of a node is the absolute value of difference between sum of nodes in it's left subtree and right subtree. \"tilt\" of the whole tree is represented as the sum of \"tilt\"s of all it's nodes. 3. Input and Output is managed for you. Note -&gt; Please refer the video for clarity.</p>","inputFormat":"Input is managed for you.","outputFormat":"Output is managed for you.","constraints":"None","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <vector>\n\nusing namespace std;\n\nclass Node\n{\npublic:\n int data=0;\n Node *left = nullptr;\n Node *right = nullptr;\n Node(int data)\n {\n this->data = data;\n }\n};\n\n class 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\n//Display function\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\n//Height function\nint height(Node *node)\n{\n return node == nullptr ? -1 : max(height(node->left), height(node->right)) + 1; // for no of edges: -1, and in terms of no of nodes return 0;\n}\n\nstatic int til = 0;\nint tilt(Node *node)\n{\n // write your code here\n}\n\nint main(){\n int n;\n cin>>n;\n \n vector<int> arr(n,0);\n for(int i = 0; i < n; i++) {\n string tmp;\n cin>>tmp;\n if (tmp==\"n\") {\n arr[i] = -1;\n } else {\n arr[i] = stoi(tmp);\n }\n }\n \n \n Node * root = constructTree(arr);\n int r = tilt(root);\n cout<<til;\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 height(Node node) {\r\n if (node == null) {\r\n return -1;\r\n }\r\n\r\n int lh = height(node.left);\r\n int rh = height(node.right);\r\n\r\n int th = Math.max(lh, rh) + 1;\r\n return th;\r\n }\r\n\r\n static int tilt = 0;\r\n public static int tilt(Node node){\r\n // write your code here to set the tilt data member\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 tilt(root);\r\n System.out.println(tilt);\r\n }\r\n\r\n}"},"python":{"code":"class Node:\n \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\ndef height(node):\n if(node == None):\n return -1\n else:\n max(height(node.left),height(node.right))+1\n return ans\n\ndef tilt(node):\n # write your code here\n \n\nn = int(input())\nst = input()\narr = [0]*n\narr = list(map(int,st.replace(\"n\",\"-1\").split(\" \")));\n\n\nroot = construct(arr)\nr = tilt(root)\nprint(Node.Tilt)"}},"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":"390","questionVideo":"https://www.youtube.com/embed/CVXfXjuBM8I","hints":[],"associated":[{"id":"4d6a1dcc-5f91-45d0-b888-e0375969830e","name":"What will be the auxiliary space complexity of \"Tilt of a Binary tree\"?","slug":"what-will-be-the-auxiliary-space-complexity-of-tilt-of-a-binary-tree","type":4},{"id":"7c193ecd-2669-4edf-8575-e9b1fc07e1b4","name":"What will be the time complexity of \"Tilt of a Binary tree\"?","slug":"what-will-be-the-time-complexity-of-tilt-of-a-binary-tree","type":4},{"id":"83aed25b-71c7-49df-b2c0-7ba5f78fd4a1","name":"Tilt of a node is the absolute value of difference between sum of nodes in it's left subtree and right subtree?","slug":"tilt-of-a-node-is-the-absolute-value-of-difference-between-sum-of-nodes-in-it-s-left-subtree-and-right-subtree","type":4},{"id":"a2d8100f-44a2-495f-a26b-b0eb9e98c9c1","name":"formula to calculate tilt of a binary tree","slug":"formula-to-calculate-tilt-of-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":"05c5235a-277a-4939-8e79-65232c71e068","name":"Tilt Of Binary Tree","slug":"tilt-of-binary-tree","type":1}],"next":{"id":"b3289da2-e27c-4fb2-8313-95716c574559","name":"Tilt of a Binary Tree","type":3,"slug":"tilt-of-a-binary-tree"},"prev":{"id":"60672207-6bbd-4fcf-bf2e-05d4dd071f63","name":"Diameter of a Binary Tree","type":3,"slug":"diameter-of-a-binary-tree"}}}
plane

Editor

Loading...

Tilt Of Binary Tree

easy

1. You are given a partially written BinaryTree class. 2. You are required to complete the body of tilt function. The function is expected to set the value of data member "tilt". "tilt" of a node is the absolute value of difference between sum of nodes in it's left subtree and right subtree. "tilt" of the whole tree is represented as the sum of "tilt"s of all it's nodes. 3. Input and Output is managed for you. Note -> Please refer the video for clarity.

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

390

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode