All Nodes Distance K in Binary Tree
Problem Description
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.valare unique. targetis the value of one of the nodes in the tree.0 <= k <= 1000
Solve it on LeetCode
Approaches
1. Convert Tree to Undirected Graph
Intuition:
The problem can be simplified by viewing the binary tree as an undirected graph. Each node can be connected to its children and, for our purposes, we can connect each child back to its parent, forming a graph-like adjacency list. Once this graph is prepared, we can perform a Breadth-First Search (BFS) to find all nodes that are exactly K distance away from the target node.
Steps:
- Build Graph: Start by performing a DFS traversal on the tree to convert it into an undirected graph, represented by an adjacency list.
- BFS Traversal: Perform a BFS starting from the target node, keeping track of visited nodes to avoid cycles. Record nodes that are exactly K edges away.
Code:
- Time Complexity: O(N) where N is the number of nodes. Constructing the graph takes O(N) and performing BFS also takes O(N).
- Space Complexity: O(N) for storing the graph and visited nodes.
2. DFS to Find Target Node and Explore Neighbors Using BFS
Intuition:
Instead of explicitly building a graph, we can use a combination of DFS and BFS directly on the tree structure. First, use DFS to find the path to the target node. Then, treat this path as the base and perform BFS from the target while marking distances in the BFS.
Steps:
- DFS to Target: Find the target node and the path leading to it by using DFS. Mark each node's distance from the root (or considered starting point).
- BFS Exploration: Use BFS from the target to find nodes at distance K. Treat any node along the path to the target as an "intermediary root" to account for upward paths.
Code:
- Time Complexity: O(N), where N is the number of nodes in the tree, since we potentially traverse the entire tree.
- Space Complexity: O(N) due to recursive stack usage in DFS calls.