## Similar Problems

Similar Problems not available

# All Nodes Distance K In Binary Tree - Leetcode Solution

## Companies:

LeetCode: All Nodes Distance K In Binary Tree Leetcode Solution

Difficulty: Medium

Topics: binary-tree tree depth-first-search breadth-first-search

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.

## All Nodes Distance K In Binary Tree Solution Code

`1`