AlgoMaster Logo

All Nodes Distance K in Binary Tree

mediumFrequency8 min readUpdated June 23, 2026

Understanding the Problem

We have a binary tree and a target node somewhere inside it. We need to find every node whose distance from the target is exactly k. Distance here means the number of edges on the path between two nodes.

Distance can run in any direction. A node at distance k from the target could be k levels down in the target's subtree, or it could sit up through the target's parent and then down some other branch. If every answer node were below the target, a DFS descending k levels from the target would be enough. The complication is the other group: a binary tree only stores pointers from parent to child, so there is no direct way to walk upward from the target toward the root. Every approach below is a different answer to that one question.

Key Constraints:

  • Number of nodes in range [1, 500] - With at most 500 nodes, even an O(n^2) algorithm would pass. The approaches below are all O(n) anyway.
  • 0 <= Node.val <= 500, all values unique - A value identifies a node unambiguously, so a graph or hash map can be keyed by value instead of by node reference. Approach 1 relies on this.
  • 0 <= k <= 1000 - k can exceed the tree's height. If no node sits at distance k, the answer is an empty list.

Approach 1: Convert the Tree to an Undirected Graph + BFS

Intuition

"Distance k in any direction" is the definition of shortest-path distance in an undirected graph. The only reason it feels awkward in a tree is that tree edges are stored one-way, from parent to child. Recording every parent-child edge in both directions in an adjacency list removes that asymmetry, and the problem becomes a standard one: starting from one vertex, find every vertex at shortest-path distance exactly k. BFS answers that directly because it explores level by level; after k rounds of expansion, the queue holds exactly the vertices k edges away from the start.

Because all node values are unique, the adjacency list can map each value to a list of neighboring values, and the BFS never touches a node pointer. One detail matters more here than in tree BFS: every edge now goes both ways, so a visited set is required. Without it, the search would oscillate between a node and its parent and report wrong distances.

This reduction is also the most general of the three approaches. Once the tree is an adjacency list, any distance question about it (nodes within distance k, the farthest node from a start point, how long a signal starting at one node takes to cover the tree) becomes a plain graph traversal.

Algorithm

  1. DFS over the tree. For every parent-child pair, append the child's value to the parent's neighbor list and the parent's value to the child's neighbor list.
  2. Initialize a queue with target.val and a visited set containing target.val.
  3. Run BFS level by level, k times: dequeue every value in the current level and enqueue its unvisited neighbors, marking them visited. Stop early if the queue empties.
  4. After k rounds, the values remaining in the queue are the answer.

Example Walkthrough

1Each parent-child pointer becomes a two-way edge: 3-5, 3-1, 5-6, 5-2, 1-0, 1-8, 2-7, 2-4. BFS starts at value 5. queue=[5], visited={5}
35start6274108
1/5

Code

The adjacency list re-stores edges the tree already has: child pointers cover two of every node's three possible neighbors, and only the parent direction is missing. The next approach records that missing direction and nothing else.

Approach 2: Parent Map + BFS

Intuition

Instead of materializing the whole graph, build only the part the tree lacks. One DFS pass records each node's parent in a hash map. With that map in hand, every node can reach all three of its neighbors: left child and right child through its own pointers, parent through the map.

BFS then runs on tree nodes directly. Starting from the target, each level expands in those three directions, and after exactly k levels every node in the frontier is at distance k from the target. As in Approach 1, a visited set keeps the search from stepping back toward the node it came from.

The map is keyed by node reference rather than by value, so this version would still work if the values were not unique.

Algorithm

  1. Do a DFS over the entire tree to build a hash map mapping each node to its parent node. The root's parent is null.
  2. Initialize a queue with the target node, and a visited set containing the target node.
  3. Run BFS for exactly k levels:
    • For each node in the current level, check its left child, right child, and parent.
    • If any of these neighbors exist and haven't been visited, add them to the queue and mark them as visited.
  4. After k levels of BFS, every node remaining in the queue is at distance k from the target. Collect their values.

Example Walkthrough

1Start BFS from target node 5. queue=[5], visited={5}
35target6274108
1/5

Code

Both approaches make one pass to build a map and a second pass to collect the answer, holding O(n) extra entries throughout. A single DFS from the root can find the same nodes with no map at all.

Approach 3: Single DFS (No Parent Map)

Intuition

The parent map exists only so that the search can walk from the target up toward the root. A DFS from the root already passes through every ancestor of the target on its way down, so the upward information can travel through return values instead of a map.

Define dfs(node) to return the distance from node to the target when the target lies in node's subtree, and -1 otherwise. The target occurs in exactly one place, so at most one child's call returns a non-negative value. When dfs(node.left) returns d, the current node is at distance d + 1 from the target, and two kinds of answer nodes become visible here: the node itself, if d + 1 equals k, and nodes in the right subtree. A node x levels below the right child is at distance d + 1 + 1 + x from the target (d edges from the target up to the left child, one edge up to the current node, one edge down to the right child, then x more). Setting d + 2 + x = k gives x = k - d - 2, so a helper findDown(start, depth) collects every node exactly depth levels below start. When k - d - 2 is negative, the ancestor is already more than k edges past the target; findDown's depth < 0 check turns those calls into no-ops.

Nodes below the target are the simplest group: when the DFS reaches the target itself, findDown(target, k) collects them directly.

Algorithm

  1. Define a helper function findDown(node, depth) that collects all nodes at exactly depth levels below node, doing nothing when depth is negative.
  2. Define the main DFS function dfs(node) that returns the distance from node to the target, or -1 if the target isn't in node's subtree.
  3. In dfs(node):
    • If node is the target, call findDown(node, k) to collect nodes k levels below the target. Return 0.
    • Recurse on the left child. If it returns distance d (not -1), the current node is at distance d+1 from the target. If d+1 == k, add the current node to the result. Otherwise, call findDown on the right subtree with depth k-d-2. Return d+1.
    • Apply the same logic when the right child's call returns a distance, searching the left subtree instead.
    • If neither child contains the target, return -1.
  4. Call dfs(root) and return the result.

Example Walkthrough

1DFS reaches node 5 (target). Call findDown(5, k=2) to search subtree.
35target found6274108
1/6

Code