All Nodes Distance K in Binary Tree Medium 0 attempts
LeetCode ↗

All Nodes Distance K in Binary Tree

Medium TreeBinary TreeDFS LeetCode

Given a binary tree, a target node, and an integer K, return all nodes at distance K from the target.

Example: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2 → Output: [7,4,1]

Sample Input
—
Sample Output
—
Constraints
  • 1 <= number of nodes <= 500
  • 0 <= Node.val <= 500
  • All values are unique
  • 0 <= k <= 1000
Topics
TreeBinary TreeDFS

BFS from Target with Parent Pointers

Build a parent map, then BFS from the target node K levels.

function distanceK(root, target, k) {
  const parents = new Map();
  function dfs(node, parent) {
    if (!node) return;
    parents.set(node, parent);
    dfs(node.left, node); dfs(node.right, node);
  }
  dfs(root, null);
  const visited = new Set(), q = [target];
  visited.add(target);
  let dist = 0;
  while (q.length && dist < k) {
    const size = q.length; dist++;
    for (let i = 0; i < size; i++) {
      const n = q.shift();
      for (const next of [n.left, n.right, parents.get(n)]) {
        if (next && !visited.has(next)) { visited.add(next); q.push(next); }
      }
    }
  }
  return q.map(n => n.val);
}

Time: O(n) | Space: O(n)

Saved in this browser only. Private to you.

JavaScript