Sum of Nodes at Distance K from Target Node
Filed under Microsoft
Free read 3 of 3Confirm node value uniqueness and whether distance includes moving up to parent nodes.
The question
Given the root of a binary tree, a target node value, and an integer k, return the sum of all node values that are at distance k from the target node.
Constraints
- The number of nodes in the tree is in the range [1, 500].
- 0 <= node.val <= 1000
- target is the value of a node in the tree.
- 0 <= k <= 1000
Examples
- Input
- root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
- Output
- 7 + 4 + 1 = 12
- Why
- Nodes at distance 2 from node 5 are 7, 4, and 1.
Approach
Confirm node value uniqueness and whether distance includes moving up to parent nodes.
Find all paths from root to target and root to other nodes to calculate distances, which is computationally expensive.
Transform the binary tree into an undirected graph by populating parent pointers (using a hash map or DFS), then run BFS outward from the target node up to distance k.
Target node not found, k = 0 returning just the target value, or tree having only one node.
Tips
- What they are testing: Test when k is 0, when target is the root, and when k exceeds the depth of the tree.
- Common mistake: Treating the tree as a directed graph instead of mapping parent pointers or converting it to an undirected graph.
Related Microsoft questions
Collected from public candidate posts and coding forums. Updated Nov 2026.