Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Nodes at distance k can be above the target too, so you need to move to parents.
  2. 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);
        }
    }
}

Solve Nodes at Distance K online · All practice problems