LARGESTVAL - Editorial

Prerequisites :- DFS

Problem :- Given an undirected connected tree with N nodes, numbered from 1 to N, and rooted at node 1, find the largest node value at each level.

Solution Approach:

The solution uses dfs for identifying the largest node value at each level in an undirected connected tree rooted at node 1.

Let’s take a look at it step by step:

  • DFS Traversal:
    • Initiate a DFS traversal from the root node (node 1).
    • During the traversal, maintain a map that stores the largest node value encountered at each level.
  • Update Maximum Node Values:
    • At each node, compare the current node value with the maximum value stored for its level.
    • Update the map with the larger value.
  • Output:
    • Once the DFS traversal is complete, output the maximum node values for each level.

Time Complexity: O(N + E) = O(N), where N is the number of nodes and E is the no. of edges in the tree. The two DFS traversals visit each node and edge once. Instead of map, an array/vector can be also used to achieve the runtime complexity.

Space Complexity: O(N), as the algorithm utilizes an array to store max value at each level and in worst case, if the tree is linear it can take upto O(N) space.