Tree Diameter

Moderate
0/80
profile
Contributed by
12 upvotes
Asked in companies
IntuitShareChat

Problem statement

Bojack had an array ‘ARR’ of size ‘N’. The ‘i’th value in the array denotes the number of child nodes is at the ‘i’th level of a tree. He wants to find out the maximum possible diameter of the tree. Help Bojack to find the diameter of the tree.

The diameter of a tree is the number of nodes in the longest path of the tree between two end nodes.

For Example : 
‘N’ = 3 ‘ARR’ = {1, 2, 3}


In this example, This is one possible way to construct a tree having one node as the root node, and 2 nodes at the first level, and 3 nodes at the second level. Hence the diameter of this tree is 5.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases. Then each test case follows.

The first line of each test case contains an integer ‘N’ denoting the height of the binary tree.

The second line of the test case contains ‘N’ integers denoting the array ‘ARR’.
Output Format : 
For each test case, print a single integer denoting the maximum possible diameter.

Output for each test case will be printed in a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.
Constraints : 
1 <= T <= 10
1 <= ‘N’ <= 1000
1 <= ‘ARR[i]’ <= 3000 where 2 <= ‘i’ <= ‘N’
ARR[0] = 1


Time Limit: 1sec
Sample Input 1 :
2
2
1 2
4
1 3 1 2
Sample Output 1 :
3
5
Explanation For Sample Output 1 :

For the First Test Case, this is the only possible way to draw a tree from the given condition. Hence the maximum possible diameter is 3.


For the second Test Case, This is one of the possible tree which can be formed from the given conditions having a diameter of 5. Hence the answer is 5.
Sample Input 2 :
2
1
1
2
1 7
Sample Output 2 :
1
3
Hint

For every level to be included in the diameter we need at least 2 nodes

Approaches (1)
Brute Force

Approach: If we think a little, We just need to check whether the current level has 1 node or 2 nodes. If the current level has one node, there can be 2 possible scenarios, first, one node of the diameter is one level before the current level, or second, the diameter can be below the current level and if the current level has 2 nodes, then the possible case scenario is that the diameter passes through both the nodes of the current level.

 

The steps are as follows:

  1. Take two integers ‘answer’, ‘count’ to store the final answer and the current maximum length of the diameter, initialize ‘answer’ and ‘count’ by ‘N’.
  2. Iterate through the whole array ‘ARR’ from 1 to ‘N’(say iterator be i):
    • If the current level has more than 1 node:
      • Update ‘count’ = ‘count’ + 1.
    • Else if the current level has only one node:
      • Update ‘count’ = ‘N’ - ‘i’.
    • Update ‘answer’ = max(‘answer’, ‘count’).
  3. Return ‘answer’.
Time Complexity

O(N), where N is the height of the tree.


As we are iterating through the whole array once and updating the value of ‘count’. Hence the time complexity will be O(N).

Space Complexity

O(1).

 

No extra space is used.

Hence the space complexity will be O(1).

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