Last Updated: 26 Mar, 2021
Maximum Average Value Of A Subtree
Moderate
Asked in companies
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.
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 :
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
Approaches
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.