Interesting Question || OA 2021 || please help
Anonymous User
1394
Interview

Problem Description

The city of Narnia represents a binary tree structure where house 1 is the root.

It is known that when a house is destroyed ( and the roads adjacent to it ), it breaks Narnia into multiple trees and generate huge amount of power.

The power generated from the destruction of a house equals the product of number of houses in each tree made by its destruction.

The house that will create the maximum power is known as a power centre and is used by the queen to charge her army.

Find the total possible houses that can become power centres

Problem Constraints
1 <= N <= 105


Input Format
The first and only argument is the root of the binary tree.


Output Format
Return an integer with total possible houses that can become power centres.


Example Input
Input1:

        1
       / \
      2   3


Input2:

        1
       / \
      2   3
         / \
        4   5
       /     \
      7       6



Example Output
Output1:

    Ans = 2


Output2:

    Ans = 1



Example Explanation
Explaination1

Power[1] = 1; Power[2] = 2 ; Power[3] = 2;
Hence 2 and 3 are possible power centres.


Explaination2

Power[1] = 5; Power[2] = 6 ; Power[3] = 8; Power[4] = 5; Power[6] = 5; Power[7] = 5;
Hence 3 is the only possible power centre.
Destroying 3 creates 3 trees {1-2}, {4-7} and {5-6}



Comments (5)