Last Updated: 25 Jun, 2021
Maximum Height Tree
Hard
Asked in companies
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.
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.
Approaches
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
Approach
We use dynamic programming to optimize the DFS approach.
For every node, we can precalculate two things.
- Maximum height while traveling downwards via its branches to the leaves.
- Maximum height when traveling upwards via its parent to any of the leaves
Optimal Substructure:
When node i is considered as a root,
- in[i] be the tree's maximum height when we travel downwards via its sub-trees and leaves.
- out[i] be the tree's maximum height while traveling upwards via its parent.
The maximum height of a tree when node i is
considered as a root will be max(in[i], out[i]).
When there are multiple branches of a parent, take the longest of all of them to count the answer.
Recurrence relation of in[i] and out[i]:
in[i] = max(1 + in[child], in[i])
out[i] = 1 + max(out[parent of i], 1 + longest path of all branches of parent of i)
Algorithm
- Make two arrays in and out of size equal to the no of nodes in the tree.
- Make the function dfs1() to calculate the in values for all nodes.
- In dfs1() we traverse the adjacent nodes of the current node in its adjacency list and store the maximum height in the variable ‘in[u]’.
- Make the function dfs2() to calculate the out values of all nodes.
- In dfs2() we traverse the adjacent nodes of the current node in its adjacency list and store the track with the largest and second largest length in it.
- Inside both dfs() functions, first mark result in respective arrays equal to the zero and then iterate over all nodes adjacent to the current node and track the max result from all of them.
- Update the in and out values for each node using dfs() functions
- Iterate over the all nodes and get the max answer for each node using the relation ANS = max(IN[i], OUT[i]).
- return the ans.
Similar problems