701248. Level of Nodes
Level of Nodes
Slug: level-of-nodes-1587115620
Difficulty: Medium
Id: 701248
Topic Tags: Graph, BFS, Data Structures, Algorithms
Company Tags: None
Summary
Given a graph and an integer k, the task is to find all nodes at level k from the root node. A node's level is its distance from the root node in a breadth-first search (BFS) traversal of the graph.
Detailed Explanation
To solve this problem, we can use BFS traversal algorithm on the given graph. We start by visiting the root node and then keep track of nodes at each level. Once we visit all nodes at a particular level, we move to the next level until we reach the kth level. For each node, we also maintain its parent node to ensure that we don't revisit any node more than once.
Here's a step-by-step breakdown of the solution:
- Initialize an empty queue and add the root node to it.
- Set the current level to 0 (since the root node is at level 0).
- While the queue is not empty:
- Dequeue the front node from the queue.
- If the dequeued node's level is equal to k, add it to the result set.
- Enqueue all the children of the dequeued node that have not been visited yet.
- Increment the current level by 1 for each child node.
- Return the result set.
Here's an example diagram:
0 (root)
/ \
1 2
/ \ / \
3 4 5 6
Level 0: 0
Level 1: 1, 2
Level 2: 3, 4, 5, 6
The time complexity of this solution is O(V + E), where V is the number of nodes and E is the number of edges in the graph. The space complexity is O(V) for storing the visited nodes and their levels.
Optimized Solutions
Java
import java.util.*;
class Node {
int val;
List<Node> children;
public Node(int val) {
this.val = val;
this.children = new ArrayList<>();
}
}
public class LevelOfNodes {
public static List<Integer> levelOrder(Node root, int k) {
if (root == null) return new ArrayList<>();
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
int currentLevel = 0;
List<Integer> result = new ArrayList<>();
while (!queue.isEmpty()) {
Node node = queue.poll();
if (node.val == k) {
result.add(node.val);
}
if (currentLevel < k) {
for (Node child : node.children) {
queue.offer(child);
}
currentLevel++;
}
}
return result;
}
}