All Nodes Distance K in Binary Tree

Medium
1931.

All Nodes Distance K in Binary Tree

All Nodes Distance K in Binary Tree is a medium coding problem on hash table, depth-first search and breadth-first search, asked in Amazon, Google, Microsoft and Meta interviews.

You are given the root of a binary tree whose node values are all distinct, the value target of one of its nodes, and an integer k.

Return the values of all nodes that are exactly k edges away from the target node — moving along tree edges in either direction, up to a parent or down to a child — sorted in ascending order.

Example 1

Input
root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output
[1,4,7]
Explanation
Two edges from 5: down to 7 and 4 (through 2), and up through 3 to 1. Sorted, that is 1, 4, 7.

Example 2

Input
root = [3,5,1,6,2,0,8,null,null,7,4], target = 7, k = 1
Output
[2]
Explanation
7 is a leaf; its only neighbour is its parent 2.

Example 3

Input
root = [1], target = 1, k = 3
Output
[]
Explanation
No node is three edges away in a one-node tree.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * 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 {number} target
 * @param {number} k
 * @return {number[]}
 */
var distanceK = function(root, target, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

All Nodes Distance K in Binary Tree — Problem & Solution

All Nodes Distance K in Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

All Nodes Distance K in Binary Tree is a medium coding problem on hash table, depth-first search and breadth-first search, asked in Amazon, Google, Microsoft and Meta interviews.

Problem statement

You are given the root of a binary tree whose node values are all distinct, the value target of one of its nodes, and an integer k.

Return the values of all nodes that are exactly k edges away from the target node — moving along tree edges in either direction, up to a parent or down to a child — sorted in ascending order.

Example 1

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output: [1,4,7]
Explanation: Two edges from 5: down to 7 and 4 (through 2), and up through 3 to 1. Sorted, that is 1, 4, 7.

Example 2

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 7, k = 1
Output: [2]
Explanation: 7 is a leaf; its only neighbour is its parent 2.

Example 3

Input: root = [1], target = 1, k = 3
Output: []
Explanation: No node is three edges away in a one-node tree.

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

Hints for All Nodes Distance K in Binary Tree

  1. Hint 1

    Going down from the target is easy; the trouble is going up, because a node does not know its parent.

  2. Hint 2

    Record every node's parent in one traversal (or turn the tree into an undirected graph). Then the tree is just a graph.

  3. Hint 3

    Run a breadth-first search from the target over children and parent links, never revisiting a node, and collect what sits at distance k.

How to solve All Nodes Distance K in Binary Tree

Distances in a tree run through parents as well as children. Once each node's neighbours — its two children and its parent — are known, the nodes at distance k are exactly BFS layer k from the target.

Approach

  1. Traverse the tree once and record, for every node, its neighbours: the parent link in both directions. Since values are distinct (and at most 500), an adjacency list indexed by value works.
  2. Run BFS from target with a dist array (−1 = unseen); stop expanding a node once it is at distance k.
  3. Collect every value whose distance is exactly k, in ascending order of value.

Why it works

Every tree edge appears in both directions in the adjacency lists, so the graph's shortest paths are the tree's paths; BFS assigns each node its true edge distance from the target, and the nodes with distance k are the answer.

Complexity

  • Time — O(n) — plus O(V) to scan values in order, V = 501 here
  • Space — O(n)

Pitfalls

  • Mark nodes as visited, or the walk bounces between a child and its parent forever.
  • k = 0 answers just the target itself; a large k can answer an empty list.
  • Return the values sorted ascending, as the statement fixes.

Reference solution

Python

from typing import List, Optional

def distanceK(root: Optional[TreeNode], target: int, k: int) -> List[int]:
    adj = {}
    stack = [root]
    adj[root.val] = []
    while stack:
        node = stack.pop()
        for child in (node.left, node.right):
            if child is not None:
                adj[child.val] = [node.val]
                adj[node.val].append(child.val)
                stack.append(child)
    dist = {target: 0}
    queue = [target]
    head = 0
    while head < len(queue):
        u = queue[head]
        head += 1
        if dist[u] == k:
            continue
        for v in adj[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                queue.append(v)
    return sorted(v for v, d in dist.items() if d == k)

Java

public static int[] distanceK(TreeNode root, int target, int k) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i <= 500; i++) adj.add(new ArrayList<>());
    link(root, adj);
    int[] dist = new int[501];
    Arrays.fill(dist, -1);
    dist[target] = 0;
    ArrayDeque<Integer> queue = new ArrayDeque<>();
    queue.add(target);
    while (!queue.isEmpty()) {
        int u = queue.poll();
        if (dist[u] == k) continue;
        for (int v : adj.get(u)) {
            if (dist[v] < 0) { dist[v] = dist[u] + 1; queue.add(v); }
        }
    }
    List<Integer> out = new ArrayList<>();
    for (int v = 0; v <= 500; v++) if (dist[v] == k) out.add(v);
    int[] res = new int[out.size()];
    for (int i = 0; i < res.length; i++) res[i] = out.get(i);
    return res;
}

static void link(TreeNode node, List<List<Integer>> adj) {
    for (TreeNode child : new TreeNode[] { node.left, node.right }) {
        if (child == null) continue;
        adj.get(node.val).add(child.val);
        adj.get(child.val).add(node.val);
        link(child, adj);
    }
}

C++

void linkTree(TreeNode* node, vector<vector<int>>& adj);

vector<int> distanceK(TreeNode* root, int target, int k) {
    vector<vector<int>> adj(501);
    linkTree(root, adj);
    vector<int> dist(501, -1);
    dist[target] = 0;
    vector<int> queue = {target};
    for (size_t h = 0; h < queue.size(); h++) {
        int u = queue[h];
        if (dist[u] == k) continue;
        for (int v : adj[u]) {
            if (dist[v] < 0) { dist[v] = dist[u] + 1; queue.push_back(v); }
        }
    }
    vector<int> out;
    for (int v = 0; v <= 500; v++) if (dist[v] == k) out.push_back(v);
    return out;
}

void linkTree(TreeNode* node, vector<vector<int>>& adj) {
    for (TreeNode* child : {node->left, node->right}) {
        if (!child) continue;
        adj[node->val].push_back(child->val);
        adj[child->val].push_back(node->val);
        linkTree(child, adj);
    }
}

JavaScript

var distanceK = function(root, target, k) {
    var adj = {};
    adj[root.val] = [];
    var stack = [root];
    while (stack.length > 0) {
        var node = stack.pop();
        var kids = [node.left, node.right];
        for (var c = 0; c < 2; c++) {
            var child = kids[c];
            if (child !== null) {
                adj[child.val] = [node.val];
                adj[node.val].push(child.val);
                stack.push(child);
            }
        }
    }
    var dist = {};
    dist[target] = 0;
    var queue = [target], out = [];
    for (var h = 0; h < queue.length; h++) {
        var u = queue[h];
        if (dist[u] === k) { out.push(u); continue; }
        for (var i = 0; i < adj[u].length; i++) {
            var v = adj[u][i];
            if (dist[v] === undefined) { dist[v] = dist[u] + 1; queue.push(v); }
        }
    }
    return out.sort(function(a, b) { return a - b; });
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 439 hash table problems · the whole catalogue

Learn the technique: Hashing: Hash Maps and Hash Sets · Depth-First Search (DFS)