Maximum Height Tree

Hard
0/120
Average time to solve is 60m
profile
Contributed by
11 upvotes
Asked in companies
BNY MellonOracleDirecti

Problem statement

You are given a tree with ‘N’ nodes and ‘N-1’ edges. Your task is to determine the tree's maximum height when we consider any arbitrary node as a root.

For Example: 
N = 4
Edges = [2 3], [4 3], [1 3]

Output: 2

Here node 4 is at a distance 2 from node 1 and if we make node 1 as a root, it will give the height of 2, which is the maximum possible in this tree.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer 'T' denoting the number of test cases to be run. Then the test cases follow.

The first line of each test contains integer 'N' denoting the number of nodes in the tree, and the following N-1 lines contain two nodes each.
Output Format: 
For each test case, print an integer denoting the tree's maximum height when we consider any arbitrary node as a root.
Note 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 50
1 <= N <= 10^4

Time Limit: 1 sec.
Sample Input 1:
2
3
1 2
2 3
5
1 4
4 2
2 3
3 5
Sample Output 1:
2
4
Explanation For Sample Output 1:
In test case 1:
In the first case, we can clearly see that if we make node 1 as a root node, it will make a tree of height 2. Hence will be 2.

In test case 2:

In the second case, if we make node 1 as a root node, it will make a tree of height 4, because the max distance node is node 5 from it, and it is at a distance 4.
Sample Input 2:
2
4
1 3 
3 4
3 2
5
1 3
3 4
3 2
2 5
Sample Output 2:
2
3
Hint

Try to find the answer for each node separately using DFS.

Approaches (2)
Bruteforce DFS

A straightforward approach would be to traverse the tree using DFS for every node and calculate the maximum height when the node is treated as the tree's root. The time complexity for the DFS traversal of a tree is O(N). The overall time complexity of DFS for all N nodes will be O(N^2).

 

Algorithm

  • Make one variable result to store the answer
  • Iterate over all nodes and call dfs function for each of the value
  • Make the dfs() function and run the function till we are not the last node of the subtree.
  • In the dfs() function we iterate on the adjacent nodes on the current node and call dfs() for them separately. And each dfs() function will return a variable mx which is max length path from that node.
  • Call dfs for each subtree of the root node and mark the max of the height of all nodes in a global variable result.
  • Return result


 

Time Complexity

O(N^2) Where N is the number of nodes in the tree.

 

Since we are iterating over each of the nodes and for each node dfs() will call will take extra O(N), so overall complexity will be O(N^2)

Space Complexity

O(N) Where N is the number of nodes in the tree.

 

Because of the size of the recursive stack during dfs calls space complexity will be of order N hence the overall space complexity will be O(N).

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