Last Updated: 17 Oct, 2021

Tree Diameter

Moderate

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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:

Take two integers ‘answer’, ‘count’ to store the final answer and the current maximum length of the diameter, initialize ‘answer’ and ‘count’ by ‘N’.
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’).
Return ‘answer’.

Solve now