All Nodes Distance K in Binary Tree

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);
        }
    }
};

The provided C++ code is a solution to find all nodes at a distance K in a binary tree. This solution uses a combination of Depth-First Search (DFS) to construct an adjacency list representation of the tree and Breadth-First Search (BFS) to find nodes at the specified distance from the target node.

Here's a breakdown of how this code works:

• Construct the TreeNode graph into an adjacency list:
  • The constructGraph function is used to convert the binary tree into a graph by creating an adjacency list. It recursively navigates through each node and its children, linking nodes to their parents, thereby allowing bidirectional traversal later in BFS.
• Traverse the adjacency list using BFS to find the result:
  • Initialize a queue for BFS starting from the target node’s value with a distance of 0.
  • Use a set to keep track of visited nodes to prevent reprocessing the same node.
  • For each node processed in the BFS, check the distance. If it equals k, add the node’s value to the result.
  • Add all unvisited neighboring nodes into the BFS queue with incremented distance.

Steps to leverage the code effectively:

1. Define a binary tree using the TreeNode structure provided in your setup.
2. Have values filled and the links between nodes correctly represented as a typical binary tree.
3. Instantiate the Solution class and call findNodesAtDistanceK with the root of the tree, the target node, and the integer k to denote distance.
4. The return of this function will be a vector of integers representing the values of nodes that are at distance k from the target node.

Ensure that the binary tree and target node are correctly assigned values to avoid null references. The approach is efficient in terms of space and time complexities, making use of both DFS for graphical conversion and BFS for targeted search, suitable for trees where nodes have unique values.

class Solution {

    public List<Integer> nodesAtDistanceK(TreeNode root, TreeNode target, int k) {
        Map<Integer, List<Integer>> adjList = new HashMap<>();
        buildGraph(root, null, adjList);

        List<Integer> result = new ArrayList<>();
        Set<Integer> seen = new HashSet<>();
        Queue<int[]> q = new LinkedList<>();

        // Initialize queue with target node and distance 0
        q.add(new int[] { target.val, 0 });
        seen.add(target.val);

        // Process the queue
        while (!q.isEmpty()) {
            int[] nodeInfo = q.poll();
            int nodeId = nodeInfo[0], dist = nodeInfo[1];

            // If reached required distance, collect the node
            if (dist == k) {
                result.add(nodeId);
                continue;
            }

            // Traverse the neighbors
            for (int neighbor : adjList.getOrDefault(nodeId, new ArrayList<>())) {
                if (!seen.contains(neighbor)) {
                    seen.add(neighbor);
                    q.add(new int[] { neighbor, dist + 1 });
                }
            }
        }

        return result;
    }

    // Helper to build graph from binary tree
    private void buildGraph(TreeNode node, TreeNode parent, Map<Integer, List<Integer>> adjList) {
        if (node != null && parent != null) {
            adjList.putIfAbsent(node.val, new ArrayList<>());
            adjList.putIfAbsent(parent.val, new ArrayList<>());
            adjList.get(node.val).add(parent.val);
            adjList.get(parent.val).add(node.val);
        }

        if (node != null && node.left != null) {
            buildGraph(node.left, node, adjList);
        }

        if (node != null && node.right != null) {
            buildGraph(node.right, node, adjList);
        }
    }
}

Find all nodes at a specified distance k from a target node in a binary tree using this Java function. The solution leverages Breadth-First Search (BFS) and a graph representation of the binary tree to efficiently determine nodes at the desired distance. Here’s a concise guide on how this implementation works:

• Build Adjacency List: Convert the binary tree into a graph using an adjacency list for effective BFS traversal. This is accomplished by the buildGraph method, which establishes relationships between each node and its parent ensuring all connections (both child-to-parent and parent-to-child) are reflected in the adjacency list.

• Initialize BFS Variables: Use a queue to manage the BFS nodes along with their current distances from the target. Also, utilize a set to track visited nodes to prevent redundant processing.

• BFS Traversal:

  1. Start with the target node and initiate its distance as 0.
  2. Process each node from the queue:
     • If the node's distance from the target equals k, add the node to the result list.
     • Otherwise, explore unvisited neighboring nodes, update their distances, and enqueue them.

• Return Result: After processing all possible paths within the distance k, return the list of nodes that meet the criteria.

This method ensures an efficient traversal by avoiding re-visits and leveraging direct access patterns made possible by the adjacency list graph representation. Whether the tree is sparse or dense, this approach systematically checks each level up to the distance k from the target node, ensuring a comprehensive and optimal solution.

class Solution:
    def nodesAtDistanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        node_map = collections.defaultdict(list)

        # Construct a graph from the binary tree nodes
        def construct_graph(current, parent):
            if current and parent:
                node_map[current.val].append(parent.val)
                node_map[parent.val].append(current.val)
            if current.left:
                construct_graph(current.left, current)
            if current.right:
                construct_graph(current.right, current)

        construct_graph(root, None)

        result = []
        seen = set([target.val])

        # BFS initialization with target node
        bfs_queue = collections.deque([(target.val, 0)])
        while bfs_queue:
            node_val, dist = bfs_queue.popleft()

            # Check if current node is at the required distance k
            if dist == k:
                result.append(node_val)
                continue

            # Explore all adjacent nodes
            for adjacent in node_map[node_val]:
                if adjacent not in seen:
                    seen.add(adjacent)
                    bfs_queue.append((adjacent, dist + 1))

        return result

To solve the problem of finding all nodes at distance K in a binary tree using Python, follow these key steps using the provided classes and methods:

1. Start by creating a graph representation of the binary tree. Use a defaultdict to store each node's value and its adjacent nodes. This setup helps in transforming the tree structure into a graph where each node knows its adjacent nodes, facilitating easier traversal.

2. Implement a helper function construct_graph that takes current and parent nodes as parameters:

   • Add the current node's value as a key to the node_map and append the parent's value to the list of its values, and vice versa.
   • Recursively call construct_graph for the left and right children of the current node.

3. Initialize the BFS traversal:

   • Begin by marking the target node's value as seen and add it to a queue with its distance initialized to 0.

4. Continue with the BFS traversal:

   • Dequeue a node and check its distance. If it matches K, add the node's value to the result list.
   • For each adjacent node that hasn't been visited (not in seen), mark it as seen and enqueue it along with the updated distance.

5. The function eventually returns a list of node values that are at distance K from the target node.

This technique efficiently locates nodes at a specified distance in a binary tree by leveraging graph traversal methods, specifically BFS, making it optimal for diverse tree structures.