All Nodes Distance K in Binary Tree

MediumTrees · Graph BFS/DFS🧩 Graph DFS LeetCode #863 ↗Updated Oct 30, 2026

Problem

You get the root of a binary tree with unique values, a node target inside it and an integer k. Return the values of every node whose distance from target is exactly k edges, where paths may go up through parents as well as down. Any order is accepted.

Inputroot = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2Output[7,4,1]

Inputroot = [1], target = 1, k = 3Output[]

1 ≤ nodes ≤ 500 · 0 ≤ Node.val ≤ 500, all distinct · target is in the tree · 0 ≤ k ≤ 1000

Try it yourself

Java

class Solution {
    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A tree is just an undirected graph whose “up” edges are hidden. Either expose them (parent map, then BFS k rings out from target) or let the recursion report how far below each ancestor the target sits and search the other side of that ancestor at the remaining depth.

PatternGraph DFS

Instinct Connected regions, all paths, reachability, cloning or 2-colouring a graph or grid: dive from a node, mark it, recurse into unvisited neighbours.

Memory hack Mark before you march: go deep, paint as you go, and back up only when every door is already painted.

Open the Graph DFS guide →

Approaches

Brute ForceRoot Paths + LCA Distance per Node

Time O(n · h) → O(n²)Space O(n)

The distance between two nodes is |pathA| + |pathB| - 2·c, where the paths start at the root and c is the length of their shared prefix (which ends at the LCA). Compute the target's root path once, then, for every node, find its root path and test whether the distance equals k.

Java

public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
    List<TreeNode> targetPath = new ArrayList<>();
    findPath(root, target, targetPath);
    List<TreeNode> all = new ArrayList<>();
    collect(root, all);
    List<Integer> res = new ArrayList<>();
    for (TreeNode node : all) {
        List<TreeNode> path = new ArrayList<>();
        findPath(root, node, path);
        int common = 0; // shared prefix length, ends at the LCA
        while (common < path.size() && common < targetPath.size()
                && path.get(common) == targetPath.get(common)) common++;
        if (path.size() + targetPath.size() - 2 * common == k) res.add(node.val);
    }
    return res;
}
private boolean findPath(TreeNode cur, TreeNode goal, List<TreeNode> path) {
    if (cur == null) return false;
    path.add(cur);
    if (cur == goal || findPath(cur.left, goal, path) || findPath(cur.right, goal, path)) {
        return true;
    }
    path.remove(path.size() - 1); // dead end: backtrack
    return false;
}
private void collect(TreeNode node, List<TreeNode> all) {
    if (node == null) return;
    all.add(node);
    collect(node.left, all);
    collect(node.right, all);
}

Pure tree reasoning with no graph conversion, but each node re-searches the tree.

BetterParent Map + BFS from Target

Time O(n)Space O(n)

One DFS records each node's parent, turning the tree into an undirected graph (left, right, parent). A BFS from target then expands one ring per round; after k rounds the queue holds exactly the nodes at distance k. A seen set stops us walking back the way we came.

Java

public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
    Map<TreeNode, TreeNode> parent = new HashMap<>();
    linkParents(root, null, parent);
    Queue<TreeNode> queue = new ArrayDeque<>();
    Set<TreeNode> seen = new HashSet<>();
    queue.offer(target);
    seen.add(target);
    for (int dist = 0; dist < k && !queue.isEmpty(); dist++) {
        int size = queue.size(); // one ring per round
        for (int i = 0; i < size; i++) {
            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> res = new ArrayList<>();
    for (TreeNode node : queue) res.add(node.val);
    return res;
}
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);
}

Linear and the easiest to explain, at the cost of a map and a set of n nodes.

OptimalSingle DFS Returning Distance to Target

Time O(n)Space O(h)

dist(node) returns how many edges below node the target is (or -1). At the target, collect its subtree at depth k. At an ancestor that is d edges above the target, either the ancestor itself is the answer (d == k) or we collect depth k - d - 1 in its other child's subtree. Every node is visited a constant number of times, and no map or set is needed.

Java

private List<Integer> res;
private TreeNode target;
private int k;

public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
    this.res = new ArrayList<>();
    this.target = target;
    this.k = k;
    dist(root);
    return res;
}
// edges from node down to target, or -1 if target is not below node
private int dist(TreeNode node) {
    if (node == null) return -1;
    if (node == target) {
        collectDown(node, k);
        return 0;
    }
    int left = dist(node.left);
    if (left >= 0) return climb(node, left + 1, node.right);
    int right = dist(node.right);
    if (right >= 0) return climb(node, right + 1, node.left);
    return -1;
}
// node is d edges above target; search its other side
private int climb(TreeNode node, int d, TreeNode otherChild) {
    if (d == k) res.add(node.val);
    else if (d < k) collectDown(otherChild, k - d - 1);
    return d;
}
private void collectDown(TreeNode node, int depth) {
    if (node == null || depth < 0) return;
    if (depth == 0) {
        res.add(node.val);
        return;
    }
    collectDown(node.left, depth - 1);
    collectDown(node.right, depth - 1);
}

Same linear time, only recursion-stack space — but the trickiest to get right.

Pro tip

Say the invariant aloud: “the return value is the distance from this node down to the target” — the rest of the code follows from it.

At a glance

Level	Approach	Time	Space
Brute Force	Root Paths + LCA Distance per Node	`O(n · h) → O(n²)`	`O(n)`
Better	Parent Map + BFS from Target	`O(n)`	`O(n)`
Optimal	Single DFS Returning Distance to Target	`O(n)`	`O(h)`

Common pitfalls

Only searching downward from target — misses nodes reached via the parent.
No seen set in the BFS → bouncing between a node and its parent forever.
In the DFS, searching the same child the target came from — double counts nodes.

Interview tips

Say “treat the tree as an undirected graph” first — it unlocks the BFS idea.
Handle k = 0 (just the target) and k larger than the tree height.
Offer the map-free DFS as a follow-up when asked to cut extra space.

Pattern

Tree → graph (parent links) + BFS rings → distances measured in any direction from a node inside a tree.

My notes saved in this browser