Solution For All Nodes Distance K In Binary Tree

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.

Step by Step Implementation For All Nodes Distance K In Binary Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    // This is a classic tree problem that can be solved using DFS. 
    // We can use a map to store the parent node for each node in the tree. 
    // Then, we can do a DFS from the target node to find all nodes that are distance K from the target. 
    // Finally, we can do a BFS from the target node to find all nodes that are distance K from the target.
    
    Map parent; 
    
    public List distanceK(TreeNode root, TreeNode target, int K) {
        parent = new HashMap(); 
        dfs(root); 
        
        Queue queue = new LinkedList(); 
        queue.add(null); 
        queue.add(target); 
        
        Set seen = new HashSet(); 
        seen.add(target); 
        seen.add(null); 
        
        int dist = 0; 
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll(); 
            if (node == null) {
                if (dist == K) {
                    List ans = new ArrayList(); 
                    for (TreeNode n: queue)
                        ans.add(n.val); 
                    return ans; 
                }
                queue.add(null); 
                dist++; 
            } else {
                if (!seen.contains(node.left)) {
                    seen.add(node.left); 
                    queue.add(node.left); 
                }
                if (!seen.contains(node.right)) {
                    seen.add(node.right); 
                    queue.add(node.right); 
                }
                TreeNode par = parent.get(node); 
                if (!seen.contains(par)) {
                    seen.add(par); 
                    queue.add(par); 
                }
            }
        }
        
        return new ArrayList(); 
    }
    
    public void dfs(TreeNode node) {
        if (node.left != null) {
            parent.put(node.left, node); 
            dfs(node.left); 
        }
        if (node.right != null) {
            parent.put(node.right, node); 
            dfs(node.right); 
        }
    }
}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, K: int) -> List[int]:
        
        # use a dictionary to store all the nodes in the tree
        # key: node, value: parent
        node_parent = dict()
        node_parent[root] = None
        
        # use a set to store all the visited nodes
        visited = set()
        
        # use a queue to do BFS
        queue = []
        queue.append(root)
        
        # do BFS to find the target node and store all the nodes in a dictionary
        while queue:
            curr = queue.pop(0)
            if curr == target:
                break
            if curr.left:
                node_parent[curr.left] = curr
                queue.append(curr.left)
            if curr.right:
                node_parent[curr.right] = curr
                queue.append(curr.right)
                
        # do BFS from the target node and stop when the distance is K
        # return the nodes at distance K from the target node
        queue = []
        queue.append(target)
        visited.add(target)
        distance = 0
        while queue:
            curr = queue.pop(0)
            if distance == K:
                return [node.val for node in queue]
            if curr.left and curr.left not in visited:
                queue.append(curr.left)
                visited.add(curr.left)
            if curr.right and curr.right not in visited:
                queue.append(curr.right)
                visited.add(curr.right)
            if node_parent[curr] and node_parent[curr] not in visited:
                queue.append(node_parent[curr])
                visited.add(node_parent[curr])
            distance += 1
        
        return []

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} target
 * @param {number} K
 * @return {number[]}
 */
var distanceK = function(root, target, K) {
    
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector distanceK(TreeNode* root, TreeNode* target, int K) {
        // do something
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public IList DistanceK(TreeNode root, TreeNode target, int K) {
        // This is a classic problem that can be solved using a breadth first search.
        // We start by doing a breadth first search from the target node. 
        // For each node in the search queue, we add its distance from the target node to a dictionary.
        // We also add its left and right child nodes to the search queue if they exist.
        // Once we have searched the entire tree, we can iterate through the dictionary and return all nodes that have a distance of K from the target node.
        
        // Create a queue for the breadth first search and a dictionary to store the distance of each node from the target node.
        Queue queue = new Queue();
        Dictionary distance = new Dictionary();
        
        // Add the target node to the queue and set its distance to 0.
        queue.Enqueue(target);
        distance.Add(target, 0);
        
        // Perform the breadth first search.
        while (queue.Count > 0)
        {
            // Get the next node in the queue.
            TreeNode node = queue.Dequeue();
            
            // If this node is the root node, we can stop the search.
            if (node == root)
            {
                break;
            }
            
            // Add the node's left and right child nodes to the queue if they exist.
            if (node.left != null)
            {
                queue.Enqueue(node.left);
                distance.Add(node.left, distance[node] + 1);
            }
            
            if (node.right != null)
            {
                queue.Enqueue(node.right);
                distance.Add(node.right, distance[node] + 1);
            }
            
            // Check if the node's parent node is in the queue.
            // If not, add it to the queue and set its distance.
            if (!queue.Contains(node.parent))
            {
                queue.Enqueue(node.parent);
                distance.Add(node.parent, distance[node] + 1);
            }
        }
        
        // Iterate through the dictionary and return all nodes that have a distance of K from the target node.
        List result = new List();
        foreach (KeyValuePair kvp in distance)
        {
            if (kvp.Value == K)
            {
                result.Add(kvp.Key.val);
            }
        }
        return result;
    }
}