Leetcode 863: All Nodes Distance K in Binary Tree
Given a binary tree, a target node within the tree, and a non-negative integer k, determine all the nodes that are exactly k edges away from the target node. Return these node values as a list in any order.
Problem
Approach
Steps
Complexity
Input: The input includes the root of a binary tree, a target node within the tree, and an integer k.
Example: root = [1,2,3,4,5,null,6], target = 2, k = 1
Constraints:
• The binary tree has between 1 and 500 nodes.
• All node values are unique and in the range [0, 500].
• The target node is guaranteed to exist in the tree.
• 0 <= k <= 1000.
Output: Return a list of all node values that are k edges away from the target node.
Example: Output: [4, 5, 1]
Constraints:
• Output can be in any order.
• If no nodes are at distance k, return an empty list.
Goal: Identify all nodes exactly k edges away from the given target node in the binary tree.
Steps:
• Store parent-child relationships of all nodes using a map.
• Perform a breadth-first search (BFS) or depth-first search (DFS) starting from the target node.
• Track visited nodes to avoid revisiting and looping.
• Stop the search when the depth equals k and collect the values of nodes at this depth.
Goal: Ensure all constraints of the input and expected output are satisfied.
Steps:
• The tree must be well-formed with no duplicate node values.
• The target node must exist within the tree.
• The value of k must be within the specified range.
Assumptions:
• The binary tree is finite with no cyclic references.
• Node values are distinct.
• The tree includes the specified target node.
• Input: Input: root = [1,2,3,4,5,null,6], target = 2, k = 1
• Explanation: Nodes at distance 1 from target node 2 are nodes 4, 5, and 1. Output: [4, 5, 1].
• Input: Input: root = [7], target = 7, k = 3
• Explanation: The tree contains only one node, so no nodes are at distance 3. Output: [].
Approach: Use a combination of DFS to track parent-child relationships and BFS to find nodes at a specified distance.
Observations:
• The problem requires traversing the tree in both directions: parent-to-child and child-to-parent.
• Using BFS will efficiently find nodes at a specific distance.
• Start by mapping parent relationships for all nodes.
• Perform a level-order traversal (BFS) from the target node to collect nodes at the required depth.
Steps:
• Create a map to store parent relationships for each node in the tree.
• Perform a DFS on the tree to populate this map.
• Start BFS traversal from the target node, tracking visited nodes.
• Collect nodes when the depth equals k and return them as the result.
Empty Inputs:
• Tree is empty (should not occur per constraints).
Large Inputs:
• Tree contains the maximum number of nodes, k is very large (e.g., k > tree height).
Special Values:
• Tree has only one node, k > 0.
Constraints:
• Ensure k = 0 returns the value of the target node.
class Solution {
map<TreeNode*, TreeNode*> mp;
set<TreeNode*> st;
vector<int> ans;
void parents(TreeNode* node) {
if(!node) return;
if(node->left) {
mp[node->left] = node;
parents(node->left);
}
if(node->right) {
mp[node->right] = node;
parents(node->right);
}
}
public:
vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
if(!root) return {};
parents(root);
dfs(target, k);
return ans;
}
void dfs(TreeNode* node, int k) {
if(st.count(node)) return;
st.insert(node);
if(k == 0) {
ans.push_back(node->val);
return;
}
if(node->left) dfs(node->left, k - 1);
if(node->right) dfs(node->right, k - 1);
if(mp[node]) dfs(mp[node], k - 1);
}
1 : Class Definition
class Solution {
Define the class 'Solution' to solve the problem of finding nodes at a distance 'k' from a target node in a binary tree.
2 : Variable Declaration
map<TreeNode*, TreeNode*> mp;
Declare a map 'mp' to store each node's parent node.
3 : Variable Declaration
set<TreeNode*> st;
Declare a set 'st' to track the visited nodes to avoid cycles.
4 : Variable Declaration
vector<int> ans;
Declare a vector 'ans' to store the values of nodes that are at a distance 'k' from the target.
5 : Method Definition
void parents(TreeNode* node) {
Define a helper method to traverse the tree and record each node's parent in the 'mp' map.
6 : Conditional Check
if(!node) return;
Check if the current node is null. If so, return to prevent further traversal.
7 : Conditional Check
if(node->left) {
Check if the current node has a left child.
8 : Map Operation
mp[node->left] = node;
Store the left child and its parent in the 'mp' map.
9 : Recursive Call
parents(node->left);
Recursively call the 'parents' method on the left child.
10 : Conditional Check
if(node->right) {
Check if the current node has a right child.
11 : Map Operation
mp[node->right] = node;
Store the right child and its parent in the 'mp' map.
12 : Recursive Call
parents(node->right);
Recursively call the 'parents' method on the right child.
13 : Public Method
public:
Declare the following methods as public members of the class.
14 : Method Definition
vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
Define the main method 'distanceK' that returns the values of nodes at a distance 'k' from the target.
15 : Base Case Check
if(!root) return {};
Check if the root node is null, and if so, return an empty vector.
16 : Helper Method Call
parents(root);
Call the 'parents' method to record the parent-child relationships.
17 : DFS Call
dfs(target, k);
Call the 'dfs' method to perform depth-first search and find all nodes at distance 'k' from the target.
18 : Return Statement
return ans;
Return the 'ans' vector containing the values of nodes at the specified distance.
19 : Method Definition
void dfs(TreeNode* node, int k) {
Define the 'dfs' method to perform a depth-first search on the tree.
20 : Set Check
if(st.count(node)) return;
Check if the node has already been visited by checking the 'st' set. If yes, return to avoid processing it again.
21 : Set Operation
st.insert(node);
Add the node to the 'st' set to mark it as visited.
22 : Base Case Check
if(k == 0) {
Check if the current depth 'k' is zero.
23 : Action on Base Case
ans.push_back(node->val);
If 'k' is zero, add the node's value to the 'ans' vector.
24 : Return Statement
return;
Return to exit the current function call once the node's value is added to 'ans'.
25 : Closing Brace
}
End the block for the base case check.
26 : Recursive DFS Calls
if(node->left) dfs(node->left, k - 1);
If the node has a left child, recursively call 'dfs' on the left child with a reduced value of 'k'.
27 : Recursive DFS Calls
if(node->right) dfs(node->right, k - 1);
If the node has a right child, recursively call 'dfs' on the right child with a reduced value of 'k'.
28 : Recursive DFS Call
if(mp[node]) dfs(mp[node], k - 1);
If a parent node exists in the 'mp' map, recursively call 'dfs' on the parent with a reduced value of 'k'.
Best Case: O(N), where N is the number of nodes in the tree.
Average Case: O(N), since each node and edge is visited once.
Worst Case: O(N), if k equals the tree height or the tree is skewed.
Description: The complexity is dominated by traversing the tree and performing BFS.
Best Case: O(1), if only the target node exists.
Worst Case: O(N), due to the parent map and BFS queue.
Description: Space usage depends on the map for parent references and BFS queue.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus