← DSA Atlas
Dedicated problem page · #863

All Nodes Distance K in Binary Tree

MediumTrees and Binary Search TreesTree to graph, then BFS by distanceParent-pointer map plus BFS
Solve on LeetCode ↗
863
MediumTrees and Binary Search TreesParent-pointer map plus BFSTree to graph, then BFS by distance

All Nodes Distance K in Binary Tree

Given the root of a binary tree, a target node, and an integer k, return the values of all nodes that are exactly distance k from the target, where distance is the number of edges on the path between two nodes. The answer may be returned in any order.

Open official problem prompt ↗
In plain English

List every node whose shortest path to the target is exactly k edges, counting movement up and down the tree.

Picture it like this

Dropping a pebble at the target node in a pond of connected rooms; the ripple expands one room per step, and you note every room the ripple reaches on step k.

Example
Input
root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output
[7,4,1]
Why
From node 5, nodes 7 and 4 are two edges down, and node 1 is two edges up-and-over through the root 3.
Constraints
The number of nodes is in the range [1, 500]0 <= Node.val <= 500All Node.val are uniquetarget is guaranteed to be in the tree0 <= k <= 1000
Pattern lesson

See the pattern, then code

Tree to graph, then BFS by distance
Recognition clue

Distance measured in both directions (up toward the root as well as down) means edges must be traversable both ways. That turns the tree into an undirected graph, and 'all nodes at distance exactly k' from a source is textbook BFS.

↗
Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. A binary tree only has downward pointers, so first record each node's parent. Then treat left, right, and parent as neighbors and BFS outward from the target; every node reached at BFS depth k is an answer.

New words, made simpleKnow these before the algorithm
Parent map
A dictionary giving each node its parent, adding the missing upward edges.
Undirected view
Treating each edge as traversable in both directions so BFS can move up as well as down.
BFS ring
The set of nodes discovered at a fixed distance from the source.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Downward-only DFS with distance

Works but the up-and-over bookkeeping (adjusting k across the ancestor path) is error prone.

Recurse and compute distances, back-propagating when target is found in a subtree.

Time O(n)Space O(n)
Best choiceParent map + BFS

Reduces the problem to plain BFS on a graph; clear and hard to get wrong.

Add upward edges via a parent map, then BFS from the target counting steps.

Time O(n)Space O(n)
The rule we keep true

Invariant

Each node is enqueued at most once (guarded by the visited set) and always with its true shortest distance from the target, because BFS explores nodes in nondecreasing distance order.

Why this is correct

Reasoning

Once every edge is bidirectional, the graph is connected and unweighted, so BFS from the target visits nodes in order of increasing edge distance. The visited set prevents revisiting the node we just came from (including back to the parent), guaranteeing each node's recorded distance is its shortest. Every node dequeued with dist == k is therefore exactly k edges away.

The algorithm in three movesSay these aloud before coding
1DFS once to build a node -> parent map

parent[5]=3, parent[2]=5 ...

2Start BFS from target with distance 0 and a visited set

BFS d1 from 5: {6,2,3}

3Expand to left child, right child, and parent, skipping visited nodes

BFS d2: {7,4,1} -> answer

4Collect all node values when the BFS distance equals k

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
30
51
12
63
24
75
46
1 · ReadDFS from root 3
2 · Askwho is each node's parent?
3 · Update stateparent[5]=3, parent[6]=5, parent[2]=5, parent[7]=2, parent[4]=2, parent[1]=3
4 · Resultupward edges ready
Key takeaway

From target 5, BFS radiates outward; the ring at distance 2 holds 7, 4, and 1.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 5-11Build the parent map

    One DFS records each node's parent so BFS can move upward.

  2. 2
    Lines 12-14Seed the BFS

    Begin at the target with distance 0 and mark it visited.

  3. 3
    Lines 16-19Collect at distance k

    When a dequeued node's distance equals k, record it and stop expanding (deeper nodes are farther).

  4. 4
    Lines 20-23Expand three neighbors

    Left child, right child, and parent, each enqueued once thanks to the visited set.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • k = 0 returns just the target's value
  • k larger than the tree's radius returns an empty list
  • target is the root (no parent to traverse)
  • target is a leaf (BFS goes only upward)
!

Common beginner mistakes

  • Forgetting to add the parent edge, so nodes above the target are missed
  • Not marking nodes visited, causing infinite back-and-forth
  • Storing parents keyed by value when values could repeat (here they are unique, but node identity is safer)
  • Continuing to expand past distance k and overcounting
Check your understanding

Why must we build a parent map before doing BFS?

More in Trees and Binary Search Trees

#104Maximum Depth of Binary TreePost-order height aggregation#543Diameter of Binary TreePost-order height with a running best#102Binary Tree Level Order TraversalLevel-by-level BFS#98Validate Binary Search TreeRange-bounded validation#236Lowest Common Ancestor of a Binary TreeBottom-up LCA search#105Construct Binary Tree from Preorder and InorderPreorder root + inorder split