All Nodes Distance K in Binary Tree

⚡ Difficulty: Medium 🏷️ Pattern: Tree → Graph + BFS 🏢 Asked at: PhonePe (OA), Amazon, Meta

Problem

Given a binary tree, a target node, and an integer k, return the values of all nodes that are exactly k edges away from the target. The distance can go up (through parents) as well as down.

Example:

        3
       / \
      5   1
     / \  / \
    6  2 0   8
      / \
     7   4

target = 5, k = 2  →  [7, 4, 1]

Approach

The core problem: trees only point down

A binary tree node knows its children but not its parent. Distance k can go upward, so we need to travel in all three directions (left, right, up).

Step 1 — turn the tree into a graph

Do one DFS to record each node’s parent in a hash map. Now every node effectively has up to 3 neighbors.

Step 2 — BFS from the target

Standard multi-directional BFS. Push the target, expand level by level, and stop after k levels. All nodes on that frontier are the answer. Track visited nodes so BFS doesn’t bounce back.

Complexity

Solution

public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
    Map<TreeNode, TreeNode> parent = new HashMap<>();
    buildParents(root, null, parent);

    Queue<TreeNode> q = new LinkedList<>();
    Set<TreeNode> seen = new HashSet<>();
    q.add(target); seen.add(target);
    int dist = 0;

    while (!q.isEmpty()) {
        if (dist == k) {
            List<Integer> res = new ArrayList<>();
            for (TreeNode n : q) res.add(n.val);
            return res;
        }
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode n = q.poll();
            for (TreeNode nb : new TreeNode[]{n.left, n.right, parent.get(n)}) {
                if (nb != null && seen.add(nb)) q.add(nb);
            }
        }
        dist++;
    }
    return new ArrayList<>();
}

private void buildParents(TreeNode node, TreeNode par, Map<TreeNode, TreeNode> parent) {
    if (node == null) return;
    parent.put(node, par);
    buildParents(node.left, node, parent);
    buildParents(node.right, node, parent);
}

from collections import deque

def distanceK(root, target, k):
    parent = {}
    def build(node, par):
        if not node: return
        parent[node] = par
        build(node.left, node)
        build(node.right, node)
    build(root, None)

    q = deque([target])
    seen = {target}
    dist = 0
    while q:
        if dist == k:
            return [n.val for n in q]
        for _ in range(len(q)):
            n = q.popleft()
            for nb in (n.left, n.right, parent[n]):
                if nb and nb not in seen:
                    seen.add(nb)
                    q.append(nb)
        dist += 1
    return []

vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
    unordered_map<TreeNode*, TreeNode*> parent;
    function<void(TreeNode*, TreeNode*)> build = [&](TreeNode* n, TreeNode* p) {
        if (!n) return;
        parent[n] = p;
        build(n->left, n); build(n->right, n);
    };
    build(root, nullptr);

    queue<TreeNode*> q; q.push(target);
    unordered_set<TreeNode*> seen{target};
    int dist = 0;
    while (!q.empty()) {
        if (dist == k) {
            vector<int> res;
            while (!q.empty()) { res.push_back(q.front()->val); q.pop(); }
            return res;
        }
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            TreeNode* n = q.front(); q.pop();
            for (TreeNode* nb : {n->left, n->right, parent[n]})
                if (nb && !seen.count(nb)) { seen.insert(nb); q.push(nb); }
        }
        dist++;
    }
    return {};
}

Try It Yourself

Write your solution and run it live in C++, Java, Python, Go, Rust, and more — right here in the browser.

Run your code to see output here.

Key Insight

Any “distance in all directions from a node” tree problem becomes trivial once you add parent pointers — the tree turns into an undirected graph and plain BFS finds the K-th frontier. The tree-to-graph conversion is the whole trick.

Follow-ups

• No extra parent map allowed? → A single DFS can compute the answer by returning the distance from target found in a subtree, but it’s fiddlier than BFS.
• Return distance ≤ k instead of == k? → Collect every frontier during BFS instead of only the k-th.

Related Problems

• Rotting Oranges (multi-source BFS)
• All Nodes Distance K (LC 863)

Drop a comment below if you want the DFS-only version 👇