All Nodes Distance K In Binary Tree - Leetcode Solution

Problem Statement:

Given the root of a binary tree, the value of a target node target, and an integer k, return an array of the values of all nodes that have a distance k from the target node.

You can return the answer in any order.

Example:

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

Output: [7,4,1]

Explanation: The nodes that are a distance 2 from the target node (with value 5) are the nodes with values 7, 4, and 1.

Solution:

To solve this problem, we need to perform a traversal of the binary tree to find all the nodes that have a distance k from the target node. The approach is to perform the following steps:

Step 1: We first need to find the target node in the binary tree. For this, we traverse the binary tree either using DFS or BFS until we find the node with value target.

Step 2: Next, we perform a DFS traversal of the binary tree to find all the nodes that are at a distance k from the target node. During the traversal, we keep track of the parent node of each node.

Step 3: After we have found all the nodes that are at a distance k from the target node, we return the values of these nodes in an array.

Let's implement the above approach in code:

Python Code:

class TreeNode:
  def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right

def find_distance_k_nodes(root, target, k):
  # Find the target node
  def find_target(root, target):
    if not root:
      return None
    if root.val == target:
      return root
    left = find_target(root.left, target)
    right = find_target(root.right, target)
    if left:
      return left
    if right:
      return right
    return None

  # DFS traversal to find all nodes at distance k
  def dfs(node, parent, k, result):
    if not node:
      return
    if k == 0:
      result.append(node.val)
      return
    if node.left and node.left != parent:
      dfs(node.left, node, k-1, result)
    if node.right and node.right != parent:
      dfs(node.right, node, k-1, result)
    if parent and parent != node.left and parent != node.right:
      dfs(parent, node, k-1, result)

  # Find the target node
  target_node = find_target(root, target)
  if not target_node:
    return []

  # DFS traversal to find all nodes at distance k from target
  result = []
  dfs(target_node, None, k, result)
  return result

Time Complexity:

The time complexity of the above solution is O(N), where N is the number of nodes in the binary tree. This is because we perform a DFS traversal of the binary tree to find all nodes that have a distance k from the target node.

Space Complexity:

The space complexity of the above solution is O(N), where N is the number of nodes in the binary tree. This is because we store the parent node for each node during the DFS traversal. We also store the result array that contains all the values of nodes that have a distance k from the target node.

1