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

Intuition

Approach:

Maintain a parent map, to go backtrack
Also maintain a visited map so that you dont travel to same node again in BFS

Links

https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/

Video Links

https://www.youtube.com/watch?v=i9ORlEy6EsI&ab_channel=takeUforward

Approach 1:

C++

class Solution {
public:
    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
        unordered_map<TreeNode*, TreeNode*> parent;
        unordered_map<TreeNode*, bool> visited;

        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
            int size = q.size();

            for(int i=0; i<size; i++){
                TreeNode* temp = q.front();
                q.pop();
                if(temp->left){
                    parent[temp->left] = temp;
                    q.push(temp->left);
                }

                if(temp->right){
                    parent[temp->right] = temp;
                    q.push(temp->right);
                }
            }
        }

        q.push(target);
        visited[target] = true;
        int current_level = 0;

        while(!q.empty()){
            int size = q.size();

            if(current_level == k)  break;
            else    current_level++;

            for(int i=0; i<size; i++){
                TreeNode *current = q.front();
                q.pop();

                if(current->left and !visited[current->left]){
                    q.push(current->left);
                    visited[current->left] = true;
                }

                if(current->right and !visited[current->right]){
                    q.push(current->right);
                    visited[current->right] = true;
                }

                if(parent[current] and !visited[parent[current]]){
                    q.push(parent[current]);
                    visited[parent[current]] = true;
                }
            }
        }

        vector<int> ans;

        while(!q.empty()){
            ans.push_back(q.front()->val);
            q.pop();
        }

        return ans;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++