{x}
blog image

All Nodes Distance K in Binary Tree

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 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 that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.

Example 2:

Input: root = [1], target = 1, k = 3
Output: []

 

Constraints:

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

Solution Explanation for LeetCode 863: All Nodes Distance K in Binary Tree

This problem asks to find all nodes in a binary tree that are exactly a distance k away from a given target node. The solutions presented leverage Depth-First Search (DFS) to build parent-child relationships and then perform another DFS or Breadth-First Search (BFS) to find nodes at the specified distance.

This approach involves two main steps:

  1. Building Parent-Child Relationships (DFS): A DFS function (parents in the code examples) is used to traverse the tree and store parent-child relationships in a dictionary/map (p). For each node, it records its parent node. This allows us to move upwards from the target node.

  2. Finding Nodes at Distance k (DFS): Another DFS function (dfs in the code examples) starts at the target node. It explores nodes in three directions for each node: left child, right child, and parent node. The k value acts as a counter, decrementing as we move away from the target. When k reaches 0, the current node is at the desired distance and its value is added to the result list. A visited set (vis) prevents cycles.

Time Complexity Analysis:

  • The first DFS (parents) visits each node once, resulting in O(N) time complexity, where N is the number of nodes in the tree.
  • The second DFS (dfs) can, in the worst case, visit all nodes again, resulting in O(N) time complexity.

Therefore, the overall time complexity is O(N).

Space Complexity Analysis:

  • The p dictionary/map stores parent-child relationships for all nodes, requiring O(N) space.
  • The vis set and the ans list also take O(N) space in the worst case.

Therefore, the overall space complexity is O(N).

This approach is very similar to Approach 1, but the second DFS (dfs2) is slightly more efficient because it only explores nodes that are not already visited.

Time Complexity Analysis: Still O(N) because both DFS functions visit each node at most once.

Space Complexity Analysis: Still O(N) for the same reasons as Approach 1.

Code Examples (Python):

Approach 1:

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        # ... (parents and dfs functions as shown previously) ...

Approach 2:

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        # ... (dfs1 and dfs2 functions as shown previously) ...

The code examples in Java, C++, Go, and TypeScript follow the same logic, with adjustments for the syntax and data structures of the respective languages. The core algorithm remains consistent across all implementations. Remember that you'll need the TreeNode definition (provided in the original problem statement) for all these code snippets to work correctly.