Binary Tree Cost

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
2 upvotes
Asked in company
LinkedIn

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3
1 2 3 -1 -1 -1 -1
6
4 2 9 3 5 -1 7 -1 -1 -1 -1 -1 -1
Sample Output 1 :
1
15
Explanation Of Sample Input 1 :
For test case 1 we have, 

 The input tree and the respective cost of each vertex is : 


So the total cost of the tree is 1.

So, we output 1.

For test case 2 we have,

The input tree and the respective cost of each vertex is : 


So the total cost of the tree is 15.

So, we output 15.
Sample Input 2 :
2
5
2 2 -1 3 1 -1 4 -1 -1 -1 -1 
4
4 1 -1 1 1 -1 -1 -1 -1
Sample Output 2 :
20
3
Hint

 Simulate the problem statement.

Approaches (2)
Brute Force

 

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.

 

Time Complexity

O(N^2)) , where ‘N’ is the number of vertices in the tree.
 

For each of the ‘N’ vertices, we are traversing the left and the right subtrees. So, the overall time complexity is O(N^2).

 

Space Complexity

O(1)

 

Constant extra space is required. Hence, the overall Space Complexity is O(1).

Code Solution
(100% EXP penalty)
Binary Tree Cost
Full screen
Console