Last Updated: 18 Nov, 2021
Binary Tree Cost
Moderate
Asked in company
You are given a binary tree consisting of ‘N’ nodes. Each node has a value associated with it. Ninja recently learned about tree algorithms and the teacher wants him to find the cost of this tree.
Ninja first finds the cost of each node of the tree. The cost of a node is the absolute difference between the sum of values in the left subtree and the right subtree of the node. The cost of the tree is the sum of the cost of all nodes of the tree.
Your task is to output the cost of the tree.
Input Format :
The first line of the input contains a single integer 'T', representing the number of test cases.
The first line of each test case contains an integer 'N', representing the number of nodes in the tree.
The third line of each test case will contain the values of the nodes of the tree in the level order form ( -1 for 'NULL' node) Refer to the example for further clarification.
Example :
Consider the binary tree
The input of the tree depicted in the image above will be like :
1
2 2
3 -1 4 5
-1 3 -1 -1 -1 -1
-1 -1
Explanation :
Level 1 :
The root node of the tree is 1
The value of the root node is 1.
Level 2 :
Left child of 1 = 2
Value of left child of 1 = 2
Right child of 1 = 3
Value of right child of 1 = 2
Level 3 :
Left child of 2 = 4
Value of left child of 2 = 3
Right child of 2 = null (-1)
Left child of 3 = 5
Value of left child of 3 = 4
Right child of 3 = 6
Value of right child of 3 = 5
Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Value of right child of 4 = 3
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)
Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)
The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.
The input ends when all nodes at the last level are null (-1).
Output format :
For each test case, output an integer denoting the cost of the tree.
Print the output of each test case in a new line.
Note :
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 5
1 <= N <= 10^5
1 <= Value of node[i] <= 10^5
It is guaranteed that the given input is a binary tree.
Time Limit : 1 sec
Approaches
Approach :
- Traverse the input tree in DFS.
- For each vertex of the tree :
- Calculate the sum of values in the left subtree.
- Calculate the sum of values in the right subtree.
- Take the absolute difference between the two.
- Add the absolute difference received for all vertices and return as result.
Algorithm :
- Initialise a variable ‘ans’ = 0.
- Traverse over each vertex ‘i’ of the tree by ‘dfs’.
- Initialise variable ‘l’ and ‘r’ as 0.
- Call the function ‘subtreeSum’ on the left and right children of vertex ‘i’.
- Initialise a variable ‘sum’ as 0.
- Add ‘A[i]’ to sum.
- Recursively call ‘subtreeSum’ on the left and right children of vertex ‘i’.
- Add to ‘sum’ the result obtained from the function call on children.
- Return ‘sum’.
- The value returned from the left child of vertex ‘i’ will be stored in ‘l’ , while that from the right child will be stored in ‘r’.
- Add to ‘ans’ the value ‘absolute( l - r )’.
- Return ‘ans’ as the final result.
Approach :
- We can think of traversing the tree in DFS fashion.
- When traversing over the left and right child of a node from the parent node, we get the sum of respective subtrees from the function call.
- When returning a function call from a node, we return the sum of the values of nodes of this subtree to the parent node.
- This way we can optimize the process of calculating the sum of the left and right subtree.
- Next, we calculate the absolute difference between the sum for each node and add this to our final result.
Algorithm :
- Initialise a global variable ‘ans’ as ‘0’.
- Call a function ‘dfs’ from the root node.
- Initialise variables ‘l’ and ‘r’ as 0.
- If the left child exists, call recursively ‘dfs’ on the left child and store the returned value in ‘l’.
- If the right child exists, call recursively ‘dfs’ on the right child and store the returned value in ‘r’.
- Add to ‘ans’ the value of ‘absolute( l - r )’.
- Return ‘ans’ as the final result.