All Nodes Distance K in Binary Tree

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

All node values are unique, and the target is guaranteed to exist. The tree is given in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

Distance-k nodes can be below the target or above it through ancestors.

A binary tree lacks parent links — add them, then BFS treating the tree as an undirected graph.

After k BFS levels from the target, the queue holds exactly the distance-k nodes.

Common doubts

Nodes at distance k can lie above the target — through its parent and into other subtrees — which downward-only traversal misses.

They give each node three neighbors (two children and a parent), turning the tree into an undirected graph where BFS finds all distance-k nodes.

It returns the distance from each node to the target; at an ancestor distance d away, it collects nodes k-d down the opposite subtree.

Interview follow-ups

· What an interviewer asks next.

Both root the tree as a graph and spread outward from a start node; burning tree asks for the time (max distance) to reach every node.

You'd pass the target node reference directly (the original LeetCode signature) instead of identifying it by value.

Fun facts

Adding parent pointers is the universal trick for turning 'distance in a rooted tree' into graph BFS.
The single-DFS solution is a neat example of returning information up the recursion to act at ancestors.

Asked at

AmazonFacebookGoogle

Frequently Sometimes Occasionally

Example 1

Input: root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], target = 5, k = 2
Output: [7, 4, 1]
Nodes 7 and 4 are two steps below 5; node 1 is two steps up-and-over through 3.

Example 2

Input: root = [1], target = 1, k = 0
Output: [1]
Distance 0 from the target is the target itself.

Constraints

- The number of nodes is in the range [1, 500] - 0 <= Node.val <= 500 - All Node.val are unique - 0 <= k <= 1000 - The target value exists in the tree

Distance in a tree spreads in three directions from a node: down-left, down-right, and up toward the parent. A rooted binary tree only has downward pointers, so the fix is to also reach the parent. Two clean ways: add parent pointers and BFS outward as if the tree were an undirected graph, or a single DFS that finds the target and, on the way back up, collects nodes at the right remaining distance on the other side.

Prerequisites

Before you start

· Concepts used directly in the solution.

Tree as a graph. Each node connects to left child, right child, and parent.

BFS by distance. Level-by-level BFS gives all nodes at a given distance.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“How is distance measured?”

Number of edges on the path; the target itself is distance 0.

“Does order matter?”

No — return the values in any order.

The ideal opening — say it like this

Distance-k nodes can be below the target or up through its ancestors, so I need to move upward too.

I record parent pointers, then BFS outward from the target k levels — the nodes on the k-th level are the answer.

Understand the problem

Worked example — tree [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], target = 5, k = 2

         3
        / \
       5   1
      / \ / \
     6  2 0  8
       / \
      7   4
from 5, distance 2: 7 and 4 (down), 1 (up through 3)
answer: [7, 4, 1]

Key observations

1Aha

Distance goes up as well as down

Ancestors and their other subtrees are reachable, so you must be able to move toward the parent.

2Aha

Parent pointers make it a graph

With parent links each node has three neighbors, and plain BFS finds all nodes at distance k.

3Aha

A single DFS can avoid the parent map

Find the target and, returning up each ancestor at distance d, collect nodes k−d down the opposite subtree.

Brute force vs optimal

	Parent pointers + BFS	Single DFS (find + collect)
Idea	Treat the tree as undirected, BFS k levels	On the way up, collect k-d down the other side
Time	O(n)	O(n)
Space	O(n)	O(height)

Both are O(n); the parent-BFS is the most intuitive to reason about. Full code is in the Approaches selector below.

Summary

Key takeaway

Give each node a parent pointer, then BFS from the target — the k-th level is the answer. Or, in one DFS, find the target and collect nodes k−d down the opposite subtree as you return up each ancestor. O(n).

wire parents with a DFS
BFS from target over {left, right, parent}, marking visited
after k levels, the queue holds the distance-k nodes