BFS and Parent Mapping Approach || Explanation || Edge Case Handling
Intuition\nThe problem asks to find all nodes that are exactly k distance away from a target node in a binary tree. My first thought is that this can be solved 
# Intuition\nThe problem asks to find all nodes that are exactly `k` distance away from a target node in a binary tree. My first thought is that this can be solved using Breadth-First Search (BFS). Starting from the target node, we can explore all the nodes at increasing distances, until we find all nodes at distance `k`. This approach ensures that we only traverse nodes up to the required distance without needing to traverse the entire tree unnecessarily.\n\nSince each node can be connected to its left child, right child, and parent, we need to establish the parent-child relationships first. After this, we can perform a BFS starting from the target node to explore nodes up to distance `k`.\n\n# Approach\n### Step 1: Parent Mapping\n- The first step is to traverse the tree to create a mapping of each node to its parent. This will help us move upwards in the tree during the BFS traversal when needed.\n- This is achieved using a helper function, where we perform a level-order traversal of the tree and store each node\u2019s parent in a hash map.\n\n### Step 2: BFS to Find Nodes at Distance `k`\n- Once the parent-child relationships are established, we start a BFS from the target node. \n- We initialize a queue that will store the nodes to be processed, and a set to keep track of visited nodes to avoid cycles during traversal (as we will traverse both children and parent nodes).\n- At each level of the BFS, we check the left child, right child, and parent of the current node (if they haven\u2019t been visited yet). We continue this process until we reach the nodes at exactly `k` distance from the target.\n\n### Edge Case Handling:\n1. **Null Tree**: If the root is `null`, return an empty list, as there are no nodes to traverse.\n2. **Target Node Not Found**: If the target node is not present in the tree, return an empty list since no nodes can be found.\n3. **k = 0**: If `k` is 0, we directly return the value of the target node itself, as the only node at distance 0 from the target is the target node itself.\n4. **Tree with Only One Node**: If the tree contains only one node and `k > 0`, return an empty list, as there are no nodes to explore at any distance greater than 0.\n\n### Step 3: Final Result\n- Once the BFS reaches level `k`, the current queue contains all nodes that are exactly `k` distance away from the target node. We extract their values and return them as the result.\n\n# Complexity\n\n- **Time Complexity**: \n  - The first part of the solution involves mapping each node to its parent, which takes linear time, i.e., $$O(n)$$, where `n` is the number of nodes in the tree.\n  - The BFS traversal also takes linear time, i.e., $$O(n)$$, as it processes each node once.\n  - Therefore, the overall time complexity is $$O(n)$$.\n\n- **Space Complexity**:\n  - We store the parent map, which takes $$O(n)$$ space.\n  - Additionally, we use a queue and a set to track nodes during the BFS traversal, both of which also take $$O(n)$$ space in the worst case.\n  - Hence, the space complexity is $$O(n)$$.\n\n\n\n# Code\n``` cpp []\nclass Solution {\npublic:\n    void match_parent(TreeNode* root, unordered_map<TreeNode*, TreeNode*>& parent) {\n        queue<TreeNode*> temp;\n        temp.push(root);\n\n        while (!temp.empty()) {\n            TreeNode* node = temp.front();\n            temp.pop();\n\n            if (node->left) {\n                parent[node->left] = node;\n                temp.push(node->left);\n            }\n\n            if (node->right) {\n                parent[node->right] = node;\n                temp.push(node->right);\n            }\n        }\n    }\n\n    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {\n        unordered_map<TreeNode*, TreeNode*> parent;\n        match_parent(root, parent);\n\n        queue<TreeNode*> temp;\n        temp.push(target);\n        unordered_map<TreeNode*, bool> seen;\n        seen[target] = true;\n\n        int cur = 0;\n\n        while (!temp.empty()) {\n            if (cur == k) break;\n            cur++;\n\n            int size = temp.size();\n\n            for (int i = 0; i < size; i++) {\n                TreeNode* node = temp.front();\n                temp.pop();\n\n                // Check the left child\n                if (node->left && !seen[node->left]) {\n                    seen[node->left] = true;\n                    temp.push(node->left);\n                }\n\n                // Check the right child\n                if (node->right && !seen[node->right]) {\n                    seen[node->right] = true;\n                    temp.push(node->right);\n                }\n\n                // Check the parent\n                if (parent[node] && !seen[parent[node]]) {\n                    seen[parent[node]] = true;\n                    temp.push(parent[node]);\n                }\n            }\n        }\n\n        vector<int> ans;\n        while (!temp.empty()) {\n            ans.push_back(temp.front()->val);\n            temp.pop();\n        }\n\n        return ans;\n    }\n};\n```\n``` java []\nclass Solution {\n    // Method to map each node to its parent\n    public void matchParent(TreeNode root, Map<TreeNode, TreeNode> parentMap) {\n        Queue<TreeNode> queue = new LinkedList<>();\n        queue.add(root);\n\n        while (!queue.isEmpty()) {\n            TreeNode node = queue.poll();\n\n            if (node.left != null) {\n                parentMap.put(node.left, node);\n                queue.add(node.left);\n            }\n\n            if (node.right != null) {\n                parentMap.put(node.right, node);\n                queue.add(node.right);\n            }\n        }\n    }\n\n    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {\n        Map<TreeNode, TreeNode> parentMap = new HashMap<>();\n        matchParent(root, parentMap);\n\n        Queue<TreeNode> queue = new LinkedList<>();\n        queue.add(target);\n        Set<TreeNode> seen = new HashSet<>();\n        seen.add(target);\n\n        int curDistance = 0;\n\n        while (!queue.isEmpty()) {\n            if (curDistance == k) break;\n            curDistance++;\n\n            int size = queue.size();\n\n            for (int i = 0; i < size; i++) {\n                TreeNode node = queue.poll();\n\n                // Check left child\n                if (node.left != null && !seen.contains(node.left)) {\n                    seen.add(node.left);\n                    queue.add(node.left);\n                }\n\n                // Check right child\n                if (node.right != null && !seen.contains(node.right)) {\n                    seen.add(node.right);\n                    queue.add(node.right);\n                }\n\n                // Check parent\n                if (parentMap.containsKey(node) && !seen.contains(parentMap.get(node))) {\n                    seen.add(parentMap.get(node));\n                    queue.add(parentMap.get(node));\n                }\n            }\n        }\n\n        List<Integer> result = new ArrayList<>();\n        while (!queue.isEmpty()) {\n            result.add(queue.poll().val);\n        }\n\n        return result;\n    }\n}\n```\n``` python []\nclass Solution:\n    # Method to map each node to its parent\n    def match_parent(self, root, parent_map):\n        queue = deque([root])\n\n        while queue:\n            node = queue.popleft()\n\n            if node.left:\n                parent_map[node.left] = node\n                queue.append(node.left)\n\n            if node.right:\n                parent_map[node.right] = node\n                queue.append(node.right)\n\n    def distanceK(self, root, target, k):\n        parent_map = {}\n        self.match_parent(root, parent_map)\n\n        queue = deque([target])\n        seen = {target}\n        cur_distance = 0\n\n        while queue:\n            if cur_distance == k:\n                break\n            cur_distance += 1\n\n            size = len(queue)\n            for _ in range(size):\n                node = queue.popleft()\n\n                # Check left child\n                if node.left and node.left not in seen:\n                    seen.add(node.left)\n                    queue.append(node.left)\n\n                # Check right child\n                if node.right and node.right not in seen:\n                    seen.add(node.right)\n                    queue.append(node.right)\n\n                # Check parent\n                if node in parent_map and parent_map[node] not in seen:\n                    seen.add(parent_map[node])\n                    queue.append(parent_map[node])\n\n        return [node.val for node in queue]\n```
['Hash Table', 'Tree', 'Breadth-First Search', 'Binary Tree', 'C++', 'Java', 'Python3']