List Every Node a Fixed Number of Steps From a Chosen Node
Solve this ProblemYou are given the root of a binary tree with distinct node values, a value target and an integer k. The distance between two nodes is the number of parent-child connections on the path joining them, and that path may go up and then down. Return the values of all nodes that are exactly k steps away from the node holding target, sorted in ascending order. If the target is missing or no node is that far away, return an empty list.
A tree node has no link to its parent, so one approach adds those links by converting the tree to a graph. The other lets the recursion report back the distance to the target and searches the sibling side of each ancestor.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100; all node values are distinct, 1 ≤ node.val ≤ 1000 - ◆
target is a value between 1 and 1000 that may or may not be in the tree; 0 ≤ k ≤ 100 - ◆
The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child - ◆
The distance between two nodes is the number of parent-child connections on the path between them (the path may go up and then down). Return the values of ALL nodes at distance exactly k from the target node, in ascending order. If the target is not in the tree, or no node is that far away, return an empty list
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Turn the Tree Into a Graph and Search Outward
GoodMoving UP the tree is the hard part, because a node does not know its parent. So make that knowledge explicit: record every parent-child pair in both directions (an adjacency list). Then run a breadth-first search starting at the target, storing each node's distance; nodes at distance k are collected and not expanded any further. Finally sort the collected values, since the search finds them in an arbitrary order. The graph and distance table cost O(n) space, and the final sort adds a log factor.
O(n log n)O(n)1class Solution {
2 public List<Integer> nodesAtDistance(TreeNode root, int target, int k) {
3 Map<Integer, List<Integer>> links = new HashMap<>();
4 connect(root, links);
5 List<Integer> out = new ArrayList<>();
6 if (root == null || (!links.containsKey(target) && root.val != target)) return out;
7 Map<Integer, Integer> dist = new HashMap<>();
8 Queue<Integer> queue = new ArrayDeque<>();
9 dist.put(target, 0);
10 queue.add(target);
11 while (!queue.isEmpty()) {
12 int cur = queue.poll();
13 if (dist.get(cur) == k) {
14 out.add(cur);
15 continue;
16 }
17 for (int next : links.getOrDefault(cur, new ArrayList<>())) {
18 if (!dist.containsKey(next)) {
19 dist.put(next, dist.get(cur) + 1);
20 queue.add(next);
21 }
22 }
23 }
24 Collections.sort(out);
25 return out;
26 }
27
28 private void connect(TreeNode node, Map<Integer, List<Integer>> links) {
29 if (node == null) return;
30 for (TreeNode child : new TreeNode[]{node.left, node.right}) {
31 if (child == null) continue;
32 links.computeIfAbsent(node.val, x -> new ArrayList<>()).add(child.val);
33 links.computeIfAbsent(child.val, x -> new ArrayList<>()).add(node.val);
34 connect(child, links);
35 }
36 }
37}Optimal — Recursion That Reports the Distance Back Up and Searches the Other Side
OptimalLet search(node) return how many steps this node is from the target — or -1 when the target is not in its subtree. When the target itself is reached, every node exactly k steps BELOW it is collected by a simple downward walk. Going back up, a node that is d steps from the target (d = its child's answer + 1) is either exactly k away (add it), or closer than k, in which case the nodes reachable through its OTHER child at depth k − d − 1 are also at distance k from the target (collect them by a downward walk). Nodes not on the path from the root to the target are never asked. Total work O(n) plus the final sort, and only the recursion stack (O(h)) as extra space — no parent links or adjacency lists.
O(n log n)O(h)1class Solution {
2 public List<Integer> nodesAtDistance(TreeNode root, int target, int k) {
3 List<Integer> out = new ArrayList<>();
4 search(root, target, k, out);
5 Collections.sort(out);
6 return out;
7 }
8
9 private int search(TreeNode node, int target, int k, List<Integer> out) {
10 if (node == null) return -1;
11 if (node.val == target) {
12 collectDown(node, k, out);
13 return 0;
14 }
15 int left = search(node.left, target, k, out);
16 if (left != -1) {
17 int d = left + 1;
18 if (d == k) out.add(node.val);
19 else if (d < k) collectDown(node.right, k - d - 1, out);
20 return d;
21 }
22 int right = search(node.right, target, k, out);
23 if (right != -1) {
24 int d = right + 1;
25 if (d == k) out.add(node.val);
26 else if (d < k) collectDown(node.left, k - d - 1, out);
27 return d;
28 }
29 return -1;
30 }
31
32 private void collectDown(TreeNode node, int depth, List<Integer> out) {
33 if (node == null || depth < 0) return;
34 if (depth == 0) {
35 out.add(node.val);
36 return;
37 }
38 collectDown(node.left, depth - 1, out);
39 collectDown(node.right, depth - 1, out);
40 }
41}