705614. Binary Tree K level sum
Binary Tree K Level Sum
Slug: binary-tree-k-level-sum3857 Difficulty: Easy Id: 705614 Topic Tags: Tree, Data Structures Company Tags: Samsung
Summary
Given a binary tree and an integer k, we need to find the sum of all nodes at level k from the root. This problem involves tree traversal and manipulation.
Detailed Explanation
The approach is to use a level order traversal (BFS) with a slight modification to keep track of the current level and calculate the sum accordingly. We can use a queue data structure to perform the BFS. For each node, we check if its level matches the given k. If it does, we add its value to the sum.
Here's the step-by-step breakdown:
- Initialize an empty queue and a variable
sumto store the result. - Enqueue the root node with its level set to 0.
- While the queue is not empty:
- Dequeue a node and calculate its level (which will be k-1 if the current level is k).
- If the level matches k, add the node's value to
sum. - Enqueue all the node's children with their levels incremented by 1.
- Return the calculated sum.
Here's an ASCII art diagram illustrating the process:
1 (0)
/ \
2(1) 3(1)
/ \ /
4(2) 5(2) 6(2)
In this example, k is set to 2. We start with the root node at level 0 and dequeue it. Since its level doesn't match k, we move on to the next node (level 1). When we encounter a node at level 2, we add its value to the sum.
Time complexity: O(N), where N is the number of nodes in the tree. Space complexity: O(M), where M is the maximum width of the tree at any given level.
Optimized Solutions
Java
import java.util.LinkedList;
import java.util.Queue;
public class BinaryTreeKLevelSum {
public int kLevelSum(Node root, int k) {
if (root == null) return 0;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
root.level = 0; // mark the root's level
int sum = 0;
while (!queue.isEmpty()) {
Node node = queue.poll();
if (node.level == k) {
sum += node.value;
}
for (Node child : node.children) {
child.level = node.level + 1; // update the child's level
queue.add(child);
}
}
return sum;
}
}