#863 All Nodes Distance K in Binary Tree
the problem
In plain words
You get the root, a node target inside the tree, and an integer k. Return the values of all nodes exactly k edges away from target — moving up to parents as well as down to children. Any order is fine.
in root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
out [7,4,1]
7 and 4 are two steps down from 5; 1 is up to 3, then down.
in root = [1], target = 1, k = 3
out []
- 1 ≤ number of nodes ≤ 500
- 0 ≤ Node.val ≤ 500, all values unique
- target is a node of the tree
- 0 ≤ k ≤ 1000
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternBFS shortest path (unweighted)Tree BFS (level order)
A tree only lets you walk down — but distance also goes up. Store every node's parent in a HashMap and the tree becomes an undirected graph. Then BFS from target: after k rounds, the queue holds exactly the answer.
solutions
From brute force to optimal
One DFS records parents; then a ring-by-ring BFS over left, right and parent, with a seen set.
- DFS: parent.put(child, node) for every edge.
- queue = [target]; seen = {target}.
- Repeat k times: poll the whole ring; offer unseen left, right and parent.
- Return the values in the queue.
One DFS for parents, then each node is offered at most once.
The parent map, the seen set and the queue.
class Solution { public List<Integer> distanceK(TreeNode root, TreeNode target, int k) { Map<TreeNode, TreeNode> parent = new HashMap<>(); linkParents(root, null, parent); // now every node can also go UP Deque<TreeNode> queue = new ArrayDeque<>(); Set<TreeNode> seen = new HashSet<>(); queue.offer(target); seen.add(target); for (int dist = 0; dist < k && !queue.isEmpty(); dist++) { // one ring per round for (int size = queue.size(); size > 0; size--) { TreeNode node = queue.poll(); for (TreeNode next : new TreeNode[] {node.left, node.right, parent.get(node)}) { if (next != null && seen.add(next)) queue.offer(next); } } } List<Integer> answer = new ArrayList<>(); for (TreeNode node : queue) answer.add(node.val); // the queue now holds ring k return answer; } private void linkParents(TreeNode node, TreeNode par, Map<TreeNode, TreeNode> parent) { if (node == null) return; parent.put(node, par); linkParents(node.left, node, parent); linkParents(node.right, node, parent); }}Dry run
distanceToTarget(node) returns how far target is below node (or −1). An ancestor at distance d checks itself (d == k) and collects nodes k − d − 1 deep in its other subtree.
- At target: collect everything k levels below; return 0.
- If the left child reports d', this node is d = d' + 1 away: add it if d == k, else collect the right subtree from depth d + 1.
- Mirror for the right child.
- Otherwise return −1.
The search visits each node once, and each subtree is collected at most once.
Only the recursion stack — no map.
class Solution { private List<Integer> answer; private TreeNode target; private int k; public List<Integer> distanceK(TreeNode root, TreeNode target, int k) { answer = new ArrayList<>(); this.target = target; this.k = k; distanceToTarget(root); return answer; } /** Edges from node down to target, or -1 if target is not in this subtree. */ private int distanceToTarget(TreeNode node) { if (node == null) return -1; if (node == target) { collect(node, 0); // everything k levels below the target return 0; } int left = distanceToTarget(node.left); if (left != -1) { // target is on my left, left + 1 edges away int d = left + 1; if (d == k) answer.add(node.val); else collect(node.right, d + 1); // search down the OTHER side return d; } int right = distanceToTarget(node.right); if (right != -1) { int d = right + 1; if (d == k) answer.add(node.val); else collect(node.left, d + 1); return d; } return -1; } /** Adds the nodes below `node` that are exactly k edges from target (node itself is dist away). */ private void collect(TreeNode node, int dist) { if (node == null || dist > k) return; if (dist == k) { answer.add(node.val); return; } collect(node.left, dist + 1); collect(node.right, dist + 1); }}in the room
How to say it in the interview
talk track
- Say the key move: "trees only point down; I'll add parent links so I can BFS in every direction."
- BFS with a
seenset, one ring per round — after k rounds the queue is the answer. - Offer the O(h)-space DFS if they ask to avoid the map.
traps
- No
seenset: from 5 you go up to 3, then straight back down to 5 — nodes get counted twice. - Searching only inside target's subtree — answers can sit above it or in a sibling subtree.
- Comparing values when you were given the node: use the
targetreference directly.
what they ask next
Follow-ups
Amount of Time for Binary Tree to Be Infected (LC 2385)?
Same parent map + BFS from the start node; the answer is the number of rounds until the queue runs empty.
Distance between two given nodes?
depth(p) + depth(q) − 2 · depth(LCA(p, q)) — see Lowest Common Ancestor in Tree Recursion.
before you submit
Edge cases to test
- k = 0 → [target.val].
- k larger than any distance in the tree → [].
- Answers above the target (through its parent) and in a sibling subtree.
practise next
Similar problems
- #236Lowest Common Ancestor of a Binary TreeMediumin Tree Recursion
- #994Rotting OrangesMediumin Graphs
- #102Binary Tree Level Order TraversalMediumin Traversals