Maximum Average Value Of A Subtree

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
21 upvotes
Asked in companies
Flipkart limitedJosh Technology Group

Problem statement

You are given a binary tree having 'N' nodes. Each node of the tree has an integer value. Your task is to find the maximum average of node values of any subtree of the given tree.

Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of input contains an integer 'T' representing the number of test cases. Then the test cases follow.

The only line of each test case contains elements in the level order form. The line consists of values of nodes separated by a single space. In case a node is 'null', we take -1 on its place.

For example, the input for the tree depicted in the below image would be :

Example Input

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation :

Level 1 :
The root node of the tree is 1.

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
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).
Note : 
The above format was just to provide clarity on how the input is formed for a given tree. 
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
Output Format: 
For each test case, print the maximum average of node values of any subtree of the given tree. Your output will be considered correct if it differs from the actual output by no more than 10^(-5).

Print the output of each test case in a separate line.
Note: 
You don’t need to print anything; It has already been taken care of.
Constraints: 
1 <= T <= 100
1 <= N <= 3000
-10^5 <= data <= 10^5 and data!=-1

Time Limit: 1 second
Sample Input 1:
2
1 2 3 4 -1 -1 -1 -1 -1
2 4 -1 6 -1 3 -1 -1 -1
Sample Output 1:
4.00000
4.50000
Explanation For Sample Output 1:
For the first test case: 
The subtree rooted at the node with value 4 has the maximum possible average, i.e., 4. Hence, the answer is 4 in this case.

For the second test case: 
The subtree rooted at the node with value 6 has 2 nodes and the sum of the node values is 9. Therefore, the average is 4.5 which is the maximum possible average. Hence, the answer is 4.5 in this case.
Sample Input 2:
2
1 1 0 -1 -1 -1 -1
5 7 2 -1 2 -1 -1 -1 -1
Sample Output 2:
1.00000
4.50000
Hint

Try to think of an approach by traversing the binary tree in post-order.

Approaches (1)
Recursive Solution

The idea is to traverse the given Binary Tree in post-order form, and in each recursive call, we will calculate the average sum of the subtree rooted at the current node. To find the average sum of a particular subtree, we need two things, i.e, the number of nodes in the subtree and the sum of those node values. 

 

These are the two values that we will return in each recursive call during the post-order traversal. Using the sum of node values of the left subtree and right subtree of the current node, and the number of nodes in the left subtree and right subtree of the current node, we can calculate the average sum value of the current node. Our final answer will be the maximum average value that we can find among all recursive calls.

 

Steps: 

 

  • Let maxAverage be a global variable that stores the maximum average value. Initialize it ws FLOAT_MIN. 
  • Let postOrderTravesal be a recursive function that takes a node currRoot as a parameter and traverses the subtree rooted at currRoot in post-order form to return the number of nodes in the subtree and the sum of the node values.
    • If currNode Node is a Null node, then we will return {0, 0} as there are no nodes in the subtree. This is the base case of the recursive function.
    • Otherwise, we will call the recursive function for the left child and right child of currRoot Node. Let the values returned by them be leftSubtreeResults and rightSubtreeResults, respectively.
    • Let currNodes and currSum be the two variables that store the number of nodes in the current subtree and the sum of the nodes respectively.
    • Set currSum as the sum of currRoot->data and the sum of node values in the left subtree and the right subtree of currRoot.
    • Set currNodes as the total number of nodes in both the left subtree and the right subtree. We will add 1 to currNodes as we are also considering the node currRoot.
    • Update maxAverage to the maximum value among maxAverage and currSum/currNodes.
    • Return {currSum, currNodes}. This will be used for calculating the average sum of the parent nodes.
  • Call the recursive function postOrderTraversal, for the root node of the tree.
  • Return the maxAverage variable.
Time Complexity

O(N), where ‘N’ is the number of nodes in the given binary tree.

 

As we are visiting each node of the binary tree only once. Hence, the overall time complexity is O(N).

Space Complexity

O(N), where ‘N’ is the number of nodes in the given binary tree.

 

In the worst case, when the given tree is a skewed tree. The recursion stack depth will be ‘N’. Hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Maximum Average Value Of A Subtree
Full screen
Console