Nodes Exactly K Hops Away
MediumTrees
Problem
Sensors are wired as a binary tree with distinct IDs, and a signal travels one hop per second along any edge, up or down. A signal starts at the sensor with ID target.
Return the IDs of all sensors reached after exactly k hops along the shortest path (that is, at distance exactly k from target). The order of the output does not matter.
Example 1
- Input:
- root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], target = 5, k = 2
- Output:
- [7, 4, 1]
7 and 4 are two hops down through 2; 1 is up to 3 then down.
Example 2
- Input:
- root = [1], target = 1, k = 3
- Output:
- []
Constraints
- 1 ≤ number of nodes ≤ 500
- 0 ≤ node.val ≤ 500, all distinct
- target is in the tree
- 0 ≤ k ≤ 1000
Hint
Show the first hint
The signal can go up as well as down. What does the tree look like if you treat every edge as two-way?
Walkthrough
How to approach it
01Clarify before coding
- Distance in edges? Yes, k = 0 means the target itself.
- Can k exceed the tree size? Yes, then the answer is empty.
- Is the target guaranteed present? Yes.
02Brute force
For every node, compute its distance to target via their lowest common ancestor and keep those at distance k.
Cost: O(n·h) or O(n²) time depending on how each distance is computed.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.