The challenge
Return values of all nodes exactly k edges from the target node.
Target identity matters when values repeat. A missing target, negative k, or empty tree gives [].
Example
From B:4 at k = 2, the balanced example returns [12]. A distance beyond the tree gives [].
Use the walkthrough below to inspect the input and each state change.
See Distance K, step by step
Follow the branches. Watch the state change.
View child pointers & node state
| Node | Value | Left | Right | State |
|---|---|---|---|---|
| A | 8 | B | C | — |
| B | 4 | D | E | — |
| C | 12 | F | G | — |
| D | 2 | null | null | — |
| E | 6 | null | null | — |
| F | 10 | null | null | — |
| G | 14 | null | null | — |
Inspect the input.
Labels identify node objects; numbers are their values. Left and right child pointers define the tree.
root = A:8View original input
A:8 [L:B, R:C] · B:4 [L:D, R:E] · C:12 [L:F, R:G] · D:2 [L:null, R:null] · E:6 [L:null, R:null] · F:10 [L:null, R:null] · G:14 [L:null, R:null]
Target: B:4 · k = 2
Node IDs stay distinct even when values repeat. Pointer mutations update the diagram; removed nodes remain in the state table for reference.
Put it into code
Build upward links, then use BFS with a visited set.
Nodes store value, left, and right. C++ uses C++17 or later.
from collections import deque
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def distance_k(root, target, k):
if root is None or target is None or k < 0:
return []
parent, stack = {root: None}, [root]
while stack:
node = stack.pop()
for child in (node.left, node.right):
if child:
parent[child] = node
stack.append(child)
if target not in parent:
return []
queue, seen = deque([target]), {target}
for _ in range(k):
if not queue:
return []
for _ in range(len(queue)):
node = queue.popleft()
for nxt in (node.left, node.right, parent[node]):
if nxt is not None and nxt not in seen:
seen.add(nxt)
queue.append(nxt)
return [node.value for node in queue]
#include <algorithm>
#include <cmath>
#include <functional>
#include <limits>
#include <map>
#include <optional>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
struct Node {
long long value;
Node *left = nullptr, *right = nullptr;
explicit Node(long long v) : value(v) {}
};
vector<long long> distance_k(Node* root, Node* target, int k) {
if (!root || !target || k < 0) return {};
unordered_map<Node*, Node*> parent; parent[root] = nullptr;
stack<Node*> todo; todo.push(root);
while (!todo.empty()) {
Node* node = todo.top(); todo.pop();
for (Node* child : {node->left, node->right}) {
if (child) { parent[child] = node; todo.push(child); }
}
}
if (!parent.count(target)) return {};
queue<Node*> pending; pending.push(target);
unordered_set<Node*> seen{target};
for (int d = 0; d < k; ++d) {
if (pending.empty()) return {};
int width = static_cast<int>(pending.size());
for (int i = 0; i < width; ++i) {
Node* node = pending.front(); pending.pop();
for (Node* next : {node->left, node->right, parent[node]}) {
if (next && seen.insert(next).second) pending.push(next);
}
}
}
vector<long long> out;
while (!pending.empty()) { out.push_back(pending.front()->value); pending.pop(); }
return out;
}