**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.