algoadvance

Leetcode 863. All Nodes Distance K in Binary Tree

Problem Statement

Given the root of a binary tree, the value of a target node in the tree, 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]

Clarifying Questions

  1. Q: Can the tree contain duplicate values?
    • A: No, values are unique.
  2. Q: What should be returned if there are no nodes at distance k?
    • A: Return an empty list.
  3. Q: How is the tree represented for input/output?
    • A: The tree is represented using the binary tree node structure, where each node has a val, left, and right.
  4. Q: Will the target node always exist in the tree?
    • A: Yes, we can assume the target node exists.

Strategy

  1. Convert the Tree to a Graph: Use a map to store the adjacency list, treating the binary tree as an undirected graph.
  2. Perform BFS from the Target Node: Using Breadth-First Search (BFS), explore nodes starting from the target node to find all nodes that are k distance away.

Steps:

  1. Tree Traversal to Graph Construction:
    • Traverse the tree and build an adjacency list representation of the graph using a map.
  2. Breadth-First Search (BFS):
    • From the target node, perform BFS to find all nodes at distance k.

Code

Here is the implementation in C++:

#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
private:
    unordered_map<int, vector<int>> graph;

    void buildGraph(TreeNode* node) {
        if (!node) return;
        if (node->left) {
            graph[node->val].push_back(node->left->val);
            graph[node->left->val].push_back(node->val);
            buildGraph(node->left);
        }
        if (node->right) {
            graph[node->val].push_back(node->right->val);
            graph[node->right->val].push_back(node->val);
            buildGraph(node->right);
        }
    }

public:
    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
        if (!root) return {};
        buildGraph(root);

        unordered_set<int> visited;
        queue<int> q;
        q.push(target->val);
        visited.insert(target->val);

        int distance = 0;

        while (!q.empty()) {
            int size = q.size();
            if (distance == k) {
                vector<int> result;
                while (!q.empty()) {
                    result.push_back(q.front());
                    q.pop();
                }
                return result;
            }
            for (int i = 0; i < size; ++i) {
                int node = q.front();
                q.pop();
                for (int neighbor : graph[node]) {
                    if (visited.find(neighbor) == visited.end()) {
                        visited.insert(neighbor);
                        q.push(neighbor);
                    }
                }
            }
            ++distance;
        }
        return {};
    }
};

Time Complexity

Overall, the time complexity is O(N).

The space complexity is also O(N) due to the space used to store the graph and the BFS queue.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI