Practice/Amazon/Leetcode 863. All Nodes Distance K in Binary Tree

Leetcode 863. All Nodes Distance K in Binary Tree

CodingMust

Problem

You are given the root of a binary tree, a reference to a specific target node within that tree, and an integer k. Your task is to find all nodes that are exactly k edges away from the target node.

The distance between two nodes is defined as the number of edges in the shortest path connecting them. Note that you can move in any direction through the tree (up to parents or down to children), effectively treating it as an undirected graph for the purposes of distance measurement.

Return a list of the values of all nodes that are at distance k from the target node. The order of values in the output list does not matter.

Requirements

1. Find all nodes exactly k edges away from the target node
2. Consider paths in all directions (not just downward in the tree)
3. Return the node values in any order
4. Handle edge cases where k is 0 or where no nodes exist at distance k

Constraints

• The number of nodes in the tree is in the range [1, 500]
• 0 ≤= Node.val ≤= 500
• All node values are unique
• The target node exists in the tree
• 0 ≤= k ≤= 1000

Examples

Example 1:

` Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2 Output: [7,4,1] Explanation: The nodes at distance 2 from target node 5 are:

• Node 7 (path: 5->2->7)
• Node 4 (path: 5->2->4)
• Node 1 (path: 5->3->1, going up through parent) `

Example 2:

Input: root = [1], target = 1, k = 3 Output: [] Explanation: There are no nodes at distance 3 from the target

Example 3:

Input: root = [1,2,3], target = 2, k = 1 Output: [1] Explanation: Node 1 is the parent of target node 2, at distance 1