DSA

All Nodes Distance K in Binary Tree

Binary Trees. Time O(n), Space O(n).

August 8, 2026
PatternTree BFS (Level Order)OptimalO(n) time · O(n) space
Solve on LeetCode
Key insighttry it first, then reveal

The problem is solved by transforming the binary tree into an undirected graph, allowing traversal in both upward (parent) and downward (child) directions.

Practice Link

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.

Approach#

The problem is solved by transforming the binary tree into an undirected graph, allowing traversal in both upward (parent) and downward (child) directions.

  • Build the Graph:
    • Use DFS to create an adjacency list from the binary tree.
    • For every node, connect it bidirectionally with its left and right children.
  • DFS Traversal from Target:
    • Perform DFS starting from the target node.
    • Use a visited set to avoid revisiting nodes.
    • At each recursive call, reduce the distance k by 1. When k == 0, collect the current node in the result list.

Implementation#

cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    void buildGraph(TreeNode* root, unordered_map<int,vector<int>>&graph)
    {
        if(!root)
            return;
        
        //link left child
        if(root->left){
            graph[root->val].push_back(root->left->val);
            graph[root->left->val].push_back(root->val);
            buildGraph(root->left, graph);
        }
        
        //link right child
        if(root->right)
        {
            graph[root->val].push_back(root->right->val);
            graph[root->right->val].push_back(root->val);
            buildGraph(root->right, graph);
        }

        //also add leaf nodes
        if (graph.find(root->val) == graph.end()) {
            graph[root->val] = {};
        }
    }

    void dfsDistanceK(unordered_map<int,vector<int>> &graph, int k, int node, vector<int> &result, vector<bool> &visited)
    {
        if(k==0){
            result.push_back(node);
            return;
        }

        visited[node] = true;

        for(int nextNode: graph[node])
        {
            if(!visited[nextNode] && k)
                dfsDistanceK(graph, k-1, nextNode, result, visited);
        }
    }

    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
        unordered_map<int,vector<int>> graph;
        buildGraph(root, graph);

        //edge cases
        if(k==0)
            return {target->val};

        vector<int> result;
        vector<bool> visited(graph.size(), false);
        dfsDistanceK(graph, k, target->val, result, visited);
        
        return result;
    }
    
};

Time Complexity: O(n)

Space Complexity: O(n)