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

All Nodes Distance K in Binary Tree

Medium TreeBinary TreeDFS LeetCode

You're given the root of a binary tree, a target node within that tree, and an integer K. Treating the tree as an undirected graph (so you can move toward parents as well as children), return the values of every node that is exactly K edges away from target.

Input Format
Implement distanceK(root, target, k). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null. The target value selects the actual node from the input tree.
Output Format
Return the result described in the statement. The order of the outer result array does not matter.

Sample Input and Output

Example 1 ยท Run Sample

Input
root = [3,5,1,6,2,0,8,null,null,7,4]
target = 5
k = 2
Output
[7,4,1]

Example 2

Input
root = [1]
target = 1
k = 0
Output
[1]
Constraints
  • 1 <= number of nodes <= 500
  • 0 <= Node.val <= 500
  • All values are unique
  • 0 <= k <= 1000
Test Cases (2)
Case 1
Args: [[3,5,1,6,2,0,8,null,null,7,4],5,2] Expected: [7,4,1]
Case 2
Args: [[1],1,0] Expected: [1]
Topics
TreeBinary TreeDFS

BFS from Target with Parent Pointers

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

javascript
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;
  let head = 0;
  while (head < q.length && dist < k) {
    const size = q.length - head; dist++;
    for (let i = 0; i < size; i++) {
      const n = q[head++];
      for (const next of [n.left, n.right, parents.get(n)]) {
        if (next && !visited.has(next)) { visited.add(next); q.push(next); }
      }
    }
  }
  return q.slice(head).map(n => n.val);
}

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

Saved in this browser only. Private to you.

JavaScript