Skip to main content

863. All Nodes Distance K in Binary Tree

medium

Return every node exactly distance K away from a target in a binary tree. The neat trick: turn the tree into an undirected graph by building parent pointers, then run BFS from the target.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given the root of a binary tree, the value of a target node target, and an integer k, return an array of the values of all nodes that have a distance k from the target node. You can return the answer in any order.

Constraints

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

Examples

Example 1

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

Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.

Example 2

Input
root = [1], target = 1, k = 3
Output
[]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

The tree is directed (parent -> child). To walk 'up' from the target, you need parent pointers.

Hint 2

First pass: DFS the tree and record each node's parent in a hash map.

Hint 3

Second pass: BFS from the target. At each step expand to left, right, AND parent. Track visited to avoid bouncing back. After k layers, the queue holds the answer.

Solution approach

Reveal approach

Two-phase: build parent map, then BFS. Phase 1 — DFS from root recording parents: helper buildParents(node, parent, parentMap) sets parentMap[node] = parent then recurses into children. Phase 2 — BFS from target: queue = [target], visited = {target}, distance = 0. Loop while queue non-empty: if distance == k, return the values of nodes in the queue. Otherwise pop the entire current layer (snapshot size) and for each node enqueue its left, right, and parentMap[node] if non-null and not in visited (adding each to visited as you enqueue). Increment distance. If you exit the loop without reaching k, return []. O(n) time and space — every node visited at most twice across the two phases.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • tree-bfs
  • tree-dfs
  • graph
  • hash-map

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Google

Practice these live with InterviewChamp.AI

Drill All Nodes Distance K in Binary Tree and Trees problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →