Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

863. All Nodes Distance K in Binary Tree - Leetcode Solution

Code Implementation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def distanceK(self, root, target, K):
        from collections import defaultdict, deque
        # Step 1: Build the graph (parent pointers)
        graph = defaultdict(list)
        def buildGraph(node, parent):
            if node:
                if parent:
                    graph[node].append(parent)
                    graph[parent].append(node)
                buildGraph(node.left, node)
                buildGraph(node.right, node)
        buildGraph(root, None)
        
        # Step 2: BFS from target
        queue = deque()
        queue.append((target, 0))
        visited = {target}
        res = []
        while queue:
            node, dist = queue.popleft()
            if dist == K:
                res.append(node.val)
            elif dist < K:
                for neighbor in graph[node]:
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append((neighbor, dist+1))
        return res
      
// Definition for a binary tree node.
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
// };
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>

class Solution {
public:
    void buildGraph(TreeNode* node, TreeNode* parent, std::unordered_map<TreeNode*, std::vector<TreeNode*>>& graph) {
        if (!node) return;
        if (parent) {
            graph[node].push_back(parent);
            graph[parent].push_back(node);
        }
        buildGraph(node->left, node, graph);
        buildGraph(node->right, node, graph);
    }
    std::vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
        std::unordered_map<TreeNode*, std::vector<TreeNode*>> graph;
        buildGraph(root, nullptr, graph);
        std::queue<std::pair<TreeNode*, int>> q;
        std::unordered_set<TreeNode*> visited;
        q.push({target, 0});
        visited.insert(target);
        std::vector<int> res;
        while (!q.empty()) {
            auto [node, dist] = q.front(); q.pop();
            if (dist == K) {
                res.push_back(node->val);
            } else if (dist < K) {
                for (auto neighbor : graph[node]) {
                    if (!visited.count(neighbor)) {
                        visited.insert(neighbor);
                        q.push({neighbor, dist + 1});
                    }
                }
            }
        }
        return res;
    }
};
      
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;

class Solution {
    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        Map<TreeNode, List<TreeNode>> graph = new HashMap<>();
        buildGraph(root, null, graph);
        Queue<TreeNode> queue = new LinkedList<>();
        Set<TreeNode> visited = new HashSet<>();
        queue.offer(target);
        visited.add(target);
        int dist = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            if (dist == K) {
                List<Integer> res = new ArrayList<>();
                for (TreeNode node : queue) res.add(node.val);
                return res;
            }
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                for (TreeNode neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                    if (!visited.contains(neighbor)) {
                        visited.add(neighbor);
                        queue.offer(neighbor);
                    }
                }
            }
            dist++;
        }
        return new ArrayList<>();
    }
    private void buildGraph(TreeNode node, TreeNode parent, Map<TreeNode, List<TreeNode>> graph) {
        if (node == null) return;
        if (parent != null) {
            graph.computeIfAbsent(node, x -> new ArrayList<>()).add(parent);
            graph.computeIfAbsent(parent, x -> new ArrayList<>()).add(node);
        }
        buildGraph(node.left, node, graph);
        buildGraph(node.right, node, graph);
    }
}
      
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} target
 * @param {number} K
 * @return {number[]}
 */
var distanceK = function(root, target, K) {
    const graph = new Map();
    function buildGraph(node, parent) {
        if (!node) return;
        if (parent) {
            if (!graph.has(node)) graph.set(node, []);
            if (!graph.has(parent)) graph.set(parent, []);
            graph.get(node).push(parent);
            graph.get(parent).push(node);
        }
        buildGraph(node.left, node);
        buildGraph(node.right, node);
    }
    buildGraph(root, null);
    const queue = [];
    const visited = new Set();
    queue.push([target, 0]);
    visited.add(target);
    const res = [];
    while (queue.length) {
        const [node, dist] = queue.shift();
        if (dist === K) {
            res.push(node.val);
        } else if (dist < K) {
            for (const neighbor of (graph.get(node) || [])) {
                if (!visited.has(neighbor)) {
                    visited.add(neighbor);
                    queue.push([neighbor, dist + 1]);
                }
            }
        }
    }
    return res;
};

Problem Description

Given the root of a binary tree, a target node, and an integer K, the task is to find all nodes in the tree that are exactly K distance away from the target node. The distance between two nodes is defined as the number of edges along the shortest path connecting them.
  • Each node has a unique value.
  • The tree is not necessarily balanced.
  • Return the values of all nodes at distance K from the target node in any order.
  • You may not reuse nodes. Each node can only be counted once.

Thought Process

To solve this problem, we first need to recognize the challenge: binary trees have parent-child relationships, but do not have pointers back to their parents. If we want to explore nodes "away" from a target, we need a way to move both downwards (to children) and upwards (to parent). A brute-force approach would be to traverse the tree from the target node, but since we can't move up to the parent without extra information, this becomes complex. A key insight is to treat the tree as an undirected graph, where each node is connected to its children and its parent. This allows us to perform a breadth-first search (BFS) starting from the target, exploring all nodes at increasing distances, just like finding nodes at level K in a graph. By building a map of parent relationships, we can efficiently move in all directions from any node.

Solution Approach

The solution uses two main steps:
  1. Build a graph representation:
    • Traverse the tree and, for each node, record its parent and children as neighbors in a graph (typically using a hash map or dictionary).
    • This allows us to move both up and down the tree from any node.
  2. Breadth-First Search (BFS) from the target node:
    • Use a queue to explore nodes level by level, starting from the target node.
    • Track visited nodes to avoid cycles.
    • When the current distance from the target is K, collect all node values at that level.

We use a hash map for the graph because it provides O(1) lookups for neighbors. BFS is chosen because it naturally finds all nodes at a given distance from the start node.

Example Walkthrough

Consider the following tree: 

        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4
  • target = 5
  • K = 2

Step 1: Build the graph
For each node, record its neighbors. For example, 5's neighbors are 3, 6, and 2.

Step 2: BFS from 5

  • Distance 0: [5]
  • Distance 1: [3, 6, 2]
  • Distance 2: [1, 7, 4] (neighbors of 3: 1; neighbors of 2: 7, 4)
At distance 2, the nodes are 7, 4, and 1. These are returned as the answer.

Time and Space Complexity

  • Brute-force approach: Without parent pointers, exploring all paths from the target to every node would be O(N^2) in the worst case, due to repeated traversals.
  • Optimized approach (BFS with parent map):
    • Building the graph: O(N), where N is the number of nodes (each node and edge is visited once).
    • BFS traversal: O(N), since each node is visited at most once.
    • Space: O(N) for the graph and O(N) for the BFS queue/visited set.

Thus, both time and space complexity are O(N).

Summary

The key to solving "All Nodes Distance K in Binary Tree" efficiently is to treat the tree as an undirected graph by recording parent relationships. This enables a simple BFS from the target node, collecting all nodes at the required distance. The solution is elegant because it leverages standard graph traversal techniques and requires only linear time and space, making it suitable even for large trees.