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.