All Nodes Distance K in Binary Tree

Problem Statement

In this problem, you are provided with the root of a binary tree, and you are tasked with finding the values of all nodes that are exactly 'k' units of distance from a specified target node. The distance is measured in terms of the number of edges between two nodes in the tree. You need to return these values as an array, and the order of values in the resulting array does not matter. This requires understanding both the structure of the tree and how to measure distances within it efficiently.

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 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

Approach and Intuition

To solve the problem efficiently, understanding the tree's structure and utilizing a breadth-first search (BFS) or depth-first search (DFS) strategy can be very effective. Here's a simple approach based on BFS:

1. Convert the Tree to a Graph Representation:

   • Since a binary tree is a special case of a graph, you can consider transforming the tree into a graph where nodes point to their parent and children. This reformation helps in easy traversal in multiple directions (upwards towards the parent and downwards to the children).

2. Find the Target Node in the Tree:

   • Traverse the tree to find the node that has the value equal to target. During this traversal, record the parent nodes for access during the BFS.

3. Perform BFS Starting from the Target Node:

   • Initialize a queue and push the target node into it along with a distance of 0.
   • While the queue is not empty, pop the node from the queue:
     • Check the distance:
       • If it equals k, record the node's value.
       • If it is greater than k, stop further traversal from this path.
     • If less than k, push the neighboring nodes (children and parent) onto the queue with incremented distance.

4. Return the Collected Values:

   • The solution nodes are those collected at distances exactly equal to k. They are then returned as an array.

Edge Cases

• If the target node equals null, or k is 0, handle these according to the tree's structure — either by returning the target node itself if k=0, or an empty list if no valid moves are available.

Considerations Given Constraints

• Given the constraints, such as the maximum number of nodes being 500 and the unique value property, the approach remains efficient.
• Large k values, especially those greater than the tree's maximum height, simply result in an empty result since no node will satisfy the distance condition.

In the provided examples:

• Example 1 outlines a common scenario with multiple levels, and the function correctly identifies three nodes at distance 2 from the target node (value 5).
• Example 2 shows a situation where the tree is a single node, and the distance k exceeds the potential maximum distance in the tree, resulting in an empty array as expected.

Solutions

class Solution {
public:
    vector<int> findNodesAtDistanceK(TreeNode* root, TreeNode* target, int k) {
        unordered_map<int, vector<int>> adjacencyList;
    
        // Generate adjacency list using DFS
        constructGraph(root, nullptr, adjacencyList);
    
        vector<int> result;
        unordered_set<int> seen;
    
        // Set up BFS using a queue starting from the target node
        queue<pair<int, int>> queueBFS;
        queueBFS.push({target->val, 0});
        seen.insert(target->val);
    
        while (!queueBFS.empty()) {
            auto currentNode = queueBFS.front();
            queueBFS.pop();
    
            int currentValue = currentNode.first;
            int currentDistance = currentNode.second;
    
            if (currentDistance == k) {
                result.push_back(currentValue);
                continue;
            }
            for (int neighbor : adjacencyList[currentValue]) {
                if (seen.find(neighbor) == seen.end()) {
                    seen.insert(neighbor);
                    queueBFS.push({neighbor, currentDistance + 1});
                }
            }
        }
        return result;
    }
    
private:
    void constructGraph(TreeNode* node, TreeNode* parent,
                        unordered_map<int, vector<int>>& adjList) {
        if (node != nullptr && parent != nullptr) {
            adjList[node->val].push_back(parent->val);
            adjList[parent->val].push_back(node->val);
        }
    
        if (node != nullptr && node->left != nullptr) {
            constructGraph(node->left, node, adjList);
        }
    
        if (node != nullptr && node->right != nullptr) {
            constructGraph(node->right, node, adjList);
        }
    }
};