Practice › Trees
Nodes at Distance K
Medium · Trees · Asked at Amazon, Meta, Microsoft, Google
All values are distinct. Print, in increasing order, the values of all nodes at distance exactly k (number of edges) from the node with value target. Print -1 if there are none.
Input
First line: k. Second line: k values — the tree in level order, -1 means no node. Third line: target k.
Output
The values in increasing order, or -1.
Constraints
- 1 ≤ number of nodes ≤ 10^4
- 0 ≤ k ≤ 10^4
- target is in the tree
Record each node's parent, then BFS from the target treating the tree as an undirected graph (children + parent).
Example 1
Input
11 3 5 1 6 2 0 8 -1 -1 7 4 5 2
Output
1 4 7
Example 2
Input
1 1 1 3
Output
-1
Hints
- Nodes at distance k can be above the target too, so you need to move to parents.
- Store every node's parent, then BFS from the target over left, right and parent links, stopping at distance k.
Approach
First traverse the tree once to record parent[node] and find the target node. Then BFS from the target, treating the tree as an undirected graph (neighbours = children + parent) with a visited set. After exactly k BFS layers, the queue holds the answer; sort the values. If the tree is not that deep, the layer is empty — print −1.
Complexity: O(n log n) time (sorting the answer) · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
struct Node {
long long val;
Node *left = nullptr, *right = nullptr;
Node(long long v) : val(v) {}
};
// Build a tree from level order where -1 means "no node".
Node *readTree() {
int k;
cin >> k;
vector<long long> v(k);
for (auto &x : v) cin >> x;
if (k == 0 || v[0] == -1) return nullptr;
Node *root = new Node(v[0]);
queue<Node *> q;
q.push(root);
int i = 1;
while (!q.empty() && i < k) {
Node *cur = q.front();
q.pop();
if (i < k && v[i] != -1) q.push(cur->left = new Node(v[i]));
i++;
if (i < k && v[i] != -1) q.push(cur->right = new Node(v[i]));
i++;
}
return root;
}
int main() {
Node *root = readTree();
long long target;
int k;
cin >> target >> k;
unordered_map<Node *, Node *> parent;
Node *start = nullptr;
queue<Node *> q;
q.push(root);
while (!q.empty()) {
Node *n = q.front();
q.pop();
if (n->val == target) start = n;
for (Node *c : {n->left, n->right})
if (c) parent[c] = n, q.push(c);
}
unordered_set<Node *> seen = {start};
vector<Node *> layer = {start};
for (int d = 0; d < k && !layer.empty(); d++) {
vector<Node *> next;
for (Node *n : layer)
for (Node *m : {n->left, n->right, parent.count(n) ? parent[n] : nullptr})
if (m && !seen.count(m)) seen.insert(m), next.push_back(m);
layer = next;
}
vector<long long> res;
for (Node *n : layer) res.push_back(n->val);
sort(res.begin(), res.end());
if (res.empty()) cout << -1 << "\n";
for (size_t i = 0; i < res.size(); i++) cout << res[i] << (i + 1 < res.size() ? " " : "\n");
return 0;
}Python solution
import sys
from collections import deque
sys.setrecursionlimit(100000)
class Node:
def __init__(self, val):
self.val, self.left, self.right = val, None, None
def build_tree(v):
"""Build a tree from level order where -1 means "no node"."""
if not v or v[0] == -1:
return None
root = Node(v[0])
q, i = deque([root]), 1
while q and i < len(v):
cur = q.popleft()
if i < len(v) and v[i] != -1:
cur.left = Node(v[i])
q.append(cur.left)
i += 1
if i < len(v) and v[i] != -1:
cur.right = Node(v[i])
q.append(cur.right)
i += 1
return root
data = list(map(int, sys.stdin.read().split()))
k = data[0]
root = build_tree(data[1 : 1 + k])
rest = data[1 + k :]
target, k = rest[0], rest[1]
parent, start, q = {root: None}, None, deque([root])
while q:
n = q.popleft()
if n.val == target:
start = n
for c in (n.left, n.right):
if c:
parent[c] = n
q.append(c)
seen, layer = {start}, [start]
for _ in range(k):
nxt = []
for n in layer:
for m in (n.left, n.right, parent[n]):
if m and m not in seen:
seen.add(m)
nxt.append(m)
layer = nxt
res = sorted(n.val for n in layer)
print(*res if res else [-1])Java solution
import java.util.*;
public class Main {
static class Node {
long val;
Node left, right;
Node(long v) { val = v; }
}
// Build a tree from level order where -1 means "no node".
static Node readTree(Scanner sc) {
int k = sc.nextInt();
long[] v = new long[k];
for (int i = 0; i < k; i++) v[i] = sc.nextLong();
if (k == 0 || v[0] == -1) return null;
Node root = new Node(v[0]);
ArrayDeque<Node> q = new ArrayDeque<>();
q.add(root);
int i = 1;
while (!q.isEmpty() && i < k) {
Node cur = q.poll();
if (i < k && v[i] != -1) q.add(cur.left = new Node(v[i]));
i++;
if (i < k && v[i] != -1) q.add(cur.right = new Node(v[i]));
i++;
}
return root;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Node root = readTree(sc);
long target = sc.nextLong();
int k = sc.nextInt();
Map<Node, Node> parent = new HashMap<>();
Node start = null;
ArrayDeque<Node> q = new ArrayDeque<>();
q.add(root);
while (!q.isEmpty()) {
Node n = q.poll();
if (n.val == target) start = n;
if (n.left != null) { parent.put(n.left, n); q.add(n.left); }
if (n.right != null) { parent.put(n.right, n); q.add(n.right); }
}
Set<Node> seen = new HashSet<>(List.of(start));
List<Node> layer = new ArrayList<>(List.of(start));
for (int d = 0; d < k && !layer.isEmpty(); d++) {
List<Node> next = new ArrayList<>();
for (Node n : layer)
for (Node m : new Node[] {n.left, n.right, parent.get(n)})
if (m != null && seen.add(m)) next.add(m);
layer = next;
}
List<Long> res = new ArrayList<>();
for (Node n : layer) res.add(n.val);
Collections.sort(res);
if (res.isEmpty()) System.out.println(-1);
else {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < res.size(); i++) sb.append(res.get(i)).append(i + 1 < res.size() ? " " : "");
System.out.println(sb);
}
}
}