Skip to main content
Talentd

All Nodes Distance K in Binary Tree - Solution & Explanation

MediumHash TableTreeDepth-First SearchBreadth-First Search22 min readAsked at: Amazon, Microsoft, Apple +13
Practice this problem

Problem Statement

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.

 

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: []

 

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

Approach Overview

Problem Overview: Given the root of a binary tree, a target node, and an integer k, return all node values that are exactly k edges away from the target. The challenge is that nodes at distance k may lie in the target’s subtree, its ancestors, or in sibling subtrees higher in the tree.

Approach 1: Breadth-First Search using Parent Map (O(n) time, O(n) space)

A binary tree normally allows traversal only downward. To move both up and down, first build a parent map that records each node’s parent using a traversal of the tree. After that, run a BFS starting from the target node. During BFS, treat the tree like an undirected graph where neighbors are left, right, and parent. Maintain a visited set to avoid revisiting nodes. Stop the BFS when the current distance equals k and collect all nodes in that level.

This approach works because BFS explores nodes level by level, so the first time you reach distance k you already have the correct nodes. The preprocessing step ensures upward traversal is possible. Time complexity is O(n) for building the parent map and running BFS. Space complexity is O(n) for the parent map, queue, and visited set. This method relies heavily on Breadth-First Search and tree traversal concepts from Binary Tree problems.

Approach 2: Depth-First Search with Backtracking (O(n) time, O(h) space)

This method avoids building an explicit parent map. Instead, run a DFS to locate the target node and track the distance while backtracking through the recursion stack. When the DFS reaches the target, collect nodes at distance k in its subtree. While returning from recursion, compute how far each ancestor is from the target. If an ancestor is d edges away, search the opposite subtree for nodes at distance k - d - 1.

The key insight is that backtracking naturally provides ancestor distances without extra data structures. Each recursive call either finds the target or returns the distance from the current node to the target. When the target lies in one subtree, the algorithm explores the other subtree to locate nodes at the remaining distance. This approach runs in O(n) time because every node is visited at most once, and uses O(h) recursion space where h is the tree height. It combines tree recursion with techniques from Depth-First Search.

Recommended for interviews: The BFS + parent map approach is the most commonly expected solution. It’s straightforward and clearly models the problem as graph traversal from the target node. Implementing the DFS backtracking solution demonstrates deeper understanding of tree recursion and distance propagation. Showing the BFS version first proves correctness quickly, while the DFS version highlights strong problem-solving skills.

Approach 1: Breadth-First Search (BFS) using Parent Map

In this method, we first traverse the tree to establish a mapping of each node to its parent. This will allow us to easily move upwards in the tree. We then perform a BFS starting from the target node to explore all nodes at distance K. Using a queue to explore nodes level by level ensures we can track the distance from the target correctly.

This C solution first constructs a parent map using DFS to track each node's parent. It then uses BFS to explore nodes at increasing distances from the target node, utilizing a queue to maintain nodes and their distances. The visited array prevents cycles in the tree traversal.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N), where N is the number of nodes, since each node is visited once. Space Complexity: O(N) for storing the parent map and the queue.

Try this approach in the editor →

Approach 2: Depth-First Search (DFS) with Backtracking

In this method, we perform a DFS from the root to find the path to the target node while also tracking parents of each node. We then use this path to initiate DFS from the target node in all possible directions (left, right, up) to find nodes that are K distance away.

In this C++ implementation, we first fill a parent map while searching the target node. Then initiate a DFS from the target node in all directions, considering kids and parents. We backtrack to ensure each node is only visited once.

Code

C++JavaPythonC#JavaScript

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N), traversing the tree requires visiting each node once. Space Complexity: O(N) for the parent map and the recursion call stack.

Try this approach in the editor →

Approach 3: DFS + Hash Table

We first use DFS to traverse the entire tree and save each node's parent node in the hash table g.

Next, we use DFS again, starting from target, to search for nodes at a distance of k both upwards and downwards, and add them to the result array.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Breadth-First Search (BFS) using Parent Map

Time Complexity: O(N), where N is the number of nodes, since each node is visited once. Space Complexity: O(N) for storing the parent map and the queue.

Depth-First Search (DFS) with Backtracking

Time Complexity: O(N), traversing the tree requires visiting each node once. Space Complexity: O(N) for the parent map and the recursion call stack.

DFS + Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
BFS with Parent MapO(n)O(n)General case. Easiest to reason about when treating the tree as an undirected graph.
DFS with BacktrackingO(n)O(h)When minimizing extra memory and demonstrating deeper recursion-based reasoning.

Video Solution

All Nodes Distance K In A Binary Tree - Performing Bidirectional Search On A Tree Using A Hashtable • Back To Back SWE • 84,867 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is All Nodes Distance K in Binary Tree easy or hard?
All Nodes Distance K in Binary Tree is classified as a Medium difficulty problem. The core challenge is recognizing that traversal must go both downward and upward from the target. Once the tree is treated like an undirected graph, a standard BFS level traversal solves it efficiently.
How to solve All Nodes Distance K in Binary Tree in O(n)?
Traverse the tree once to record parent pointers for every node. Then perform a BFS starting from the target node while expanding to its left child, right child, and parent. Track visited nodes to avoid cycles and stop when the BFS level equals k. The nodes in that level form the result, giving an overall O(n) solution.
All Nodes Distance K in Binary Tree Python or Java solution
In Python or Java, the typical implementation builds a HashMap or dictionary mapping each node to its parent, then runs a BFS using a queue starting from the target node. Each BFS level represents one edge distance. Once the level equals k, collect the node values and return them.
What is the best approach for All Nodes Distance K in Binary Tree?
The most common solution uses Breadth-First Search with a parent map. First build a mapping from each node to its parent, then start a BFS from the target node and explore left, right, and parent neighbors. When the BFS reaches distance k, all nodes at that level are the answer. This approach runs in O(n) time and O(n) space.
What data structure is used in All Nodes Distance K in Binary Tree?
The common solution uses a hash map to store parent pointers and a queue for Breadth-First Search. A visited set prevents revisiting nodes when moving between parent and child links. The alternative DFS solution relies on recursion and distance propagation during backtracking.
What is the time complexity of All Nodes Distance K in Binary Tree?
The optimal solutions run in O(n) time where n is the number of nodes in the tree. Each node is visited at most once either during the parent map construction or the traversal that finds nodes at distance k. Space complexity is O(n) for the BFS approach or O(h) for the DFS backtracking approach, where h is the tree height.
Is All Nodes Distance K in Binary Tree asked at Google Amazon or Meta?
This problem is a classic binary tree traversal question frequently asked in technical interviews at large companies including Google, Amazon, and Meta. It tests understanding of tree traversal, BFS levels, and how to convert a tree into a graph-like structure using parent references.

Ready to solve this problem?

Practice All Nodes Distance K in Binary Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Amount of Time for Binary Tree to Be Infected