863 · All Nodes Distance K in Binary Tree

A binary tree only has pointers going down. Distance, though, doesn't care which way an edge points — so the first real step of this problem is to stop treating the tree as a tree and start treating it as an undirected graph.

1 — The problem

Given a target node and a distance K, return every node exactly K edges away — where "away" is measured along the tree's edges in either direction: down into children, or up into the parent (and from there, potentially back down a sibling subtree). A plain top-down DFS or BFS from the root has no way to go "up", because TreeNode only stores left and right — never parent.

The fix is two separate, boring passes, not one clever one: first walk the whole tree once to record every node's parent in a map. That map turns the tree into a graph you can BFS in any direction. Then BFS outward from the target, treating left, right and parent as three equally valid neighbours, and stop the instant the frontier reaches depth K.

2 — Visualizing the graph BFS

The example below plants the target in the middle of the tree, not at the root or a leaf, so the outward search genuinely has to climb before it can descend again on the other side.

Map<TreeNode, TreeNode> parent = new HashMap<>();buildParentMap(root, null, parent); // one DFS passSet<TreeNode> visited = new HashSet<>();Queue<TreeNode> frontier = new LinkedList<>();frontier.add(target); visited.add(target);int depth = 0;while (!frontier.isEmpty() && depth < k) {    int sz = frontier.size();    for (int i = 0; i < sz; i++) {        TreeNode nd = frontier.poll();        for (TreeNode nb : List.of(nd.left, nd.right, parent.get(nd))) {            if (nb != null && visited.add(nb)) frontier.add(nb);        }    }    depth++;}

The highlighted edges at the final frame trace the whole answer: two hops down from 5 to 7 and 4, and two hops up and back down from 5 through 3 to reach 1 — a path that never touches a single left/right pointer from 1's own perspective, because it's approached from its parent, not its children.

3 — Complexity and edge cases

• Time: O(n) — building the parent map visits every node once, and the outward BFS visits every node at most once too, since visited guards against re-entering the subtree you just came from.
• Space: O(n) for the parent map, plus O(n) worst case for the queue and the visited set (a very wide "distance-K ball" can approach the size of the tree).
• K = 0: the answer is just the target itself — the loop body never runs.
• Target is the root or a leaf: the algorithm doesn't need to special-case this at all; parent.get(root) is simply absent from the map, which the nb != null check already handles.
• K larger than the tree's diameter: the frontier empties out before reaching depth K and the loop exits early via frontier.isEmpty() — the answer is correctly empty, not an error.
• One-pass alternative: a single DFS can solve this without an explicit parent map, by having each call return "how far is the target from here, or −1 if it's not in this subtree" and, on the way back up, checking whether K − that distance lands inside the *other* child's subtree. It's a genuinely elegant O(n) one-pass solution, but it's also easy to get subtly wrong under interview pressure — the two-pass version above is the one to reach for first, and the one-pass version is worth attempting only once the two-pass mechanics are completely automatic.

4 — Reference implementation

public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
    Map<TreeNode, TreeNode> parent = new HashMap<>();
    buildParentMap(root, null, parent);

    Set<TreeNode> visited = new HashSet<>();
    Queue<TreeNode> frontier = new LinkedList<>();
    frontier.add(target);
    visited.add(target);

    int depth = 0;
    while (!frontier.isEmpty() && depth < k) {
        int sz = frontier.size();
        for (int i = 0; i < sz; i++) {
            TreeNode nd = frontier.poll();
            for (TreeNode nb : List.of(nd.left, nd.right, parent.get(nd))) {
                if (nb != null && visited.add(nb)) frontier.add(nb);
            }
        }
        depth++;
    }
    return frontier.stream().map(nd -> nd.val).toList();
}

private void buildParentMap(TreeNode nd, TreeNode par, Map<TreeNode, TreeNode> parent) {
    if (nd == null) return;
    parent.put(nd, par);
    buildParentMap(nd.left, nd, parent);
    buildParentMap(nd.right, nd, parent);
}