All Nodes Distance K in Binary Tree solution and explanation
Google
8 more videos on this problem
All Nodes Distance K in Binary Tree | Approach-1 | Leetcode-863 | AMAZON | Explanation ➕ Live CodingcodestorywithMIK · 21:59 · 24K views
ALL NODES DISTANCE K IN BINARY TREE | PYTHON | LEETCODE # 863Cracking FAANG · 15:41 · 16K views
All nodes distance K in binary tree | Leetcode #863Techdose · 12:45 · 14K views
LeetCode 863. All Nodes Distance K in Binary TreeHappy Coding · 15:19 · 4K views
All Nodes Distance K in Binary Tree - Leetcode 863 - PythonTechError · 8:39 · 1K views
863. All Nodes Distance K in Binary Tree | TreesDeep Tech · 11:38 · 1K views
LeetCode 863 All Nodes Distance K in Binary TreeJeevan Kumar - Cracckify · 10:17 · 1K views
Google Coding Interview Question | Leetcode 863 | All Nodes Distance K in Binary TreeWorkWithGoogler · 23:15 · 1K views
Daily Leetcode #1197: Jul 11, 2023 - 863. All Nodes Distance K in Binary TreeProgramming Live with Larry · 10:12 · 885 views
The problem
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.valare unique. targetis the value of one of the nodes in the tree.0 <= k <= 1000
Approach overview
Problem Overview: Given the root of a binary tree, a target node, and an integer k, return all node values that are exactly k edges away from the target. The challenge is that nodes at distance k may lie in the target’s subtree, its ancestors, or in sibling subtrees higher in the tree.
Approach 1: Breadth-First Search using Parent Map (O(n) time, O(n) space)
A binary tree normally allows traversal only downward. To move both up and down, first build a parent map that records each node’s parent using a traversal of the tree. After that, run a BFS starting from the target node. During BFS, treat the tree like an undirected graph where neighbors are left, right, and parent. Maintain a visited set to avoid revisiting nodes. Stop the BFS when the current distance equals k and collect all nodes in that level.
This approach works because BFS explores nodes level by level, so the first time you reach distance k you already have the correct nodes. The preprocessing step ensures upward traversal is possible. Time complexity is O(n) for building the parent map and running BFS. Space complexity is O(n) for the parent map, queue, and visited set. This method relies heavily on Breadth-First Search and tree traversal concepts from Binary Tree problems.
Approach 2: Depth-First Search with Backtracking (O(n) time, O(h) space)
This method avoids building an explicit parent map. Instead, run a DFS to locate the target node and track the distance while backtracking through the recursion stack. When the DFS reaches the target, collect nodes at distance k in its subtree. While returning from recursion, compute how far each ancestor is from the target. If an ancestor is d edges away, search the opposite subtree for nodes at distance k - d - 1.
The key insight is that backtracking naturally provides ancestor distances without extra data structures. Each recursive call either finds the target or returns the distance from the current node to the target. When the target lies in one subtree, the algorithm explores the other subtree to locate nodes at the remaining distance. This approach runs in O(n) time because every node is visited at most once, and uses O(h) recursion space where h is the tree height. It combines tree recursion with techniques from Depth-First Search.
Recommended for interviews: The BFS + parent map approach is the most commonly expected solution. It’s straightforward and clearly models the problem as graph traversal from the target node. Implementing the DFS backtracking solution demonstrates deeper understanding of tree recursion and distance propagation. Showing the BFS version first proves correctness quickly, while the DFS version highlights strong problem-solving skills.
Approach 1: Breadth-First Search (BFS) using Parent Map
In this method, we first traverse the tree to establish a mapping of each node to its parent. This will allow us to easily move upwards in the tree. We then perform a BFS starting from the target node to explore all nodes at distance K. Using a queue to explore nodes level by level ensures we can track the distance from the target correctly.
from collections import deque, defaultdict
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def distanceK(self, root, target, K):
parent_map = {}
self.buildParentMap(root, None, parent_map)
queue = deque([target])
visited = set([target])
current_level = 0
while queue:
if current_level == K:
return [node.val for node in queue]
size = len(queue)
for i in range(size):
node = queue.popleft()
for neighbor in (node.left, node.right, parent_map.get(node, None)):
if neighbor and neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
current_level += 1
return []
def buildParentMap(self, node, parent, parent_map):
if node:
parent_map[node] = parent
self.buildParentMap(node.left, node, parent_map)
self.buildParentMap(node.right, node, parent_map)import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
Map<TreeNode, TreeNode> parentMap = new HashMap<>();
buildParentMap(root, parentMap);
Queue<TreeNode> queue = new LinkedList<>();
Set<TreeNode> visited = new HashSet<>();
queue.add(target);
visited.add(target);
int currentLevel = 0;
while (!queue.isEmpty()) {
if (currentLevel == K) {
List<Integer> result = new ArrayList<>();
for (TreeNode node : queue) {
result.add(node.val);
}
return result;
}
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null && !visited.contains(node.left)) {
queue.add(node.left);
visited.add(node.left);
}
if (node.right != null && !visited.contains(node.right)) {
queue.add(node.right);
visited.add(node.right);
}
if (parentMap.containsKey(node) && !visited.contains(parentMap.get(node))) {
queue.add(parentMap.get(node));
visited.add(parentMap.get(node));
}
}
currentLevel++;
}
return new ArrayList<>();
}
private void buildParentMap(TreeNode node, Map<TreeNode, TreeNode> parentMap) {
if (node.left != null) {
parentMap.put(node.left, node);
buildParentMap(node.left, parentMap);
}
if (node.right != null) {
parentMap.put(node.right, node);
buildParentMap(node.right, parentMap);
}
}
}#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void buildParentMap(TreeNode* root, unordered_map<TreeNode*, TreeNode*>& parentMap) {
if (!root) return;
if (root->left) {
parentMap[root->left] = root;
buildParentMap(root->left, parentMap);
}
if (root->right) {
parentMap[root->right] = root;
buildParentMap(root->right, parentMap);
}
}
vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
unordered_map<TreeNode*, TreeNode*> parentMap;
buildParentMap(root, parentMap);
queue<pair<TreeNode*, int>> q;
unordered_set<TreeNode*> visited;
q.push({target, 0});
visited.insert(target);
vector<int> result;
while (!q.empty()) {
pair<TreeNode*, int> current = q.front(); q.pop();
TreeNode* node = current.first;
int distance = current.second;
if (distance == K) {
result.push_back(node->val);
}
if (distance > K) break;
// Check left child
if (node->left && !visited.count(node->left)) {
q.push({node->left, distance + 1});
visited.insert(node->left);
}
// Check right child
if (node->right && !visited.count(node->right)) {
q.push({node->right, distance + 1});
visited.insert(node->right);
}
// Check parent
if (parentMap.find(node) != parentMap.end() && !visited.count(parentMap[node])) {
q.push({parentMap[node], distance + 1});
visited.insert(parentMap[node]);
}
}
return result;
}function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
var distanceK = function(root, target, K) {
const parentMap = new Map();
const buildParentMap = (node, parent) => {
if (node) {
parentMap.set(node, parent);
buildParentMap(node.left, node);
buildParentMap(node.right, node);
}
};
buildParentMap(root, null);
const queue = [target];
const visited = new Set([target]);
let currentLevel = 0;
while (queue.length) {
if (currentLevel === K) {
return queue.map(node => node.val);
}
const size = queue.length;
for (let i = 0; i < size; i++) {
const node = queue.shift();
const directions = [node.left, node.right, parentMap.get(node)];
for (const neighbor of directions) {
if (neighbor && !visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
currentLevel++;
}
return [];
};#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
// Define the TreeNode structure
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// A node in the queue
struct QueueNode {
struct TreeNode *node;
int distance;
};
// Create a new tree node
struct TreeNode* newTreeNode(int val) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->val = val;
node->left = node->right = NULL;
return node;
}
// A simple queue implementation
#define MAX_QUEUE_SIZE 1000
typedef struct {
struct QueueNode data[MAX_QUEUE_SIZE];
int front, rear;
} Queue;
void initQueue(Queue *q) {
q->front = q->rear = 0;
}
bool isQueueEmpty(Queue *q) {
return q->front == q->rear;
}
void enqueue(Queue *q, struct TreeNode *node, int distance) {
q->data[q->rear].node = node;
q->data[q->rear].distance = distance;
q->rear++;
}
struct QueueNode dequeue(Queue *q) {
return q->data[q->front++];
}
// Helper function for DFS that creates a map from node value to parent node
void populateParentMap(struct TreeNode *root, struct TreeNode *parent, struct TreeNode **parentMap) {
if (root == NULL) return;
parentMap[root->val] = parent;
populateParentMap(root->left, root, parentMap);
populateParentMap(root->right, root, parentMap);
}
// BFS to find all nodes at distance K
void findNodesAtDistance(struct TreeNode *target, int K, struct TreeNode **parentMap, int *result, int *returnSize) {
Queue q;
initQueue(&q);
bool visited[501] = {false};
enqueue(&q, target, 0);
visited[target->val] = true;
while (!isQueueEmpty(&q)) {
struct QueueNode current = dequeue(&q);
struct TreeNode *currNode = current.node;
int currDistance = current.distance;
if (currDistance == K) {
result[(*returnSize)++] = currNode->val;
}
if (currDistance > K) break;
// Check left child
if (currNode->left && !visited[currNode->left->val]) {
enqueue(&q, currNode->left, currDistance + 1);
visited[currNode->left->val] = true;
}
// Check right child
if (currNode->right && !visited[currNode->right->val]) {
enqueue(&q, currNode->right, currDistance + 1);
visited[currNode->right->val] = true;
}
// Check parent
struct TreeNode *parent = parentMap[currNode->val];
if (parent && !visited[parent->val]) {
enqueue(&q, parent, currDistance + 1);
visited[parent->val] = true;
}
}
}
int* distanceK(struct TreeNode* root, struct TreeNode* target, int K, int* returnSize) {
struct TreeNode *parentMap[501] = {NULL};
int *result = malloc(500 * sizeof(int));
*returnSize = 0;
populateParentMap(root, NULL, parentMap);
findNodesAtDistance(target, K, parentMap, result, returnSize);
return result;
}using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public IList<int> DistanceK(TreeNode root, TreeNode target, int K) {
var parentMap = new Dictionary<TreeNode, TreeNode>();
BuildParentMap(root, parentMap);
var queue = new Queue<TreeNode>();
var visited = new HashSet<TreeNode>();
queue.Enqueue(target);
visited.Add(target);
int currentLevel = 0;
while (queue.Count > 0) {
if (currentLevel == K) {
var result = new List<int>();
foreach (var node in queue) {
result.Add(node.val);
}
return result;
}
int size = queue.Count;
for (int i = 0; i < size; i++) {
var node = queue.Dequeue();
foreach (var neighbor in new[] { node.left, node.right, parentMap.ContainsKey(node) ? parentMap[node] : null }) {
if (neighbor != null && !visited.Contains(neighbor)) {
visited.Add(neighbor);
queue.Enqueue(neighbor);
}
}
}
currentLevel++;
}
return new List<int>();
}
private void BuildParentMap(TreeNode node, Dictionary<TreeNode, TreeNode> parentMap) {
if (node.left != null) {
parentMap[node.left] = node;
BuildParentMap(node.left, parentMap);
}
if (node.right != null) {
parentMap[node.right] = node;
BuildParentMap(node.right, parentMap);
}
}
}This Python solution establishes a map associating each node to its parent. Utilizing BFS from the target node, it systematically checks left, right, and parent nodes while avoiding revisiting by recording visited nodes.
Time Complexity: O(N), where N is the number of nodes, since all nodes might be visited. Space Complexity: O(N) for parent map and queue.
Approach 2: Depth-First Search (DFS) with Backtracking
In this method, we perform a DFS from the root to find the path to the target node while also tracking parents of each node. We then use this path to initiate DFS from the target node in all possible directions (left, right, up) to find nodes that are K distance away.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def distanceK(self, root, target, K):
parent_map = {}
self.populateParentMap(root, None, parent_map)
result = []
visited = set()
self.dfs(target, K, visited, parent_map, result)
return result
def populateParentMap(self, node, parent, parent_map):
if node:
parent_map[node] = parent
self.populateParentMap(node.left, node, parent_map)
self.populateParentMap(node.right, node, parent_map)
def dfs(self, node, K, visited, parent_map, result):
if not node or node in visited:
return
visited.add(node)
if K == 0:
result.append(node.val)
return
self.dfs(node.left, K - 1, visited, parent_map, result)
self.dfs(node.right, K - 1, visited, parent_map, result)
self.dfs(parent_map[node], K - 1, visited, parent_map, result)import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
Map<TreeNode, TreeNode> parentMap = new HashMap<>();
List<Integer> result = new ArrayList<>();
populateParentMap(root, null, parentMap);
Set<TreeNode> visited = new HashSet<>();
dfs(target, null, K, visited, parentMap, result);
return result;
}
private void populateParentMap(TreeNode node, TreeNode parent, Map<TreeNode, TreeNode> parentMap) {
if (node != null) {
parentMap.put(node, parent);
populateParentMap(node.left, node, parentMap);
populateParentMap(node.right, node, parentMap);
}
}
private void dfs(TreeNode node, TreeNode parent, int K, Set<TreeNode> visited, Map<TreeNode, TreeNode> parentMap, List<Integer> result) {
if (node == null || visited.contains(node) || K < 0) return;
visited.add(node);
if (K == 0) {
result.add(node.val);
return;
}
if (node.left != parent) dfs(node.left, node, K - 1, visited, parentMap, result);
if (node.right != parent) dfs(node.right, node, K - 1, visited, parentMap, result);
TreeNode parentNode = parentMap.get(node);
if (parentNode != null && parentNode != parent) dfs(parentNode, node, K - 1, visited, parentMap, result);
}
}#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void findChildrenAtDistance(TreeNode* node, int K, vector<int>& result, unordered_set<TreeNode*>& visited) {
if (!node || visited.count(node)) return;
if (K == 0) {
result.push_back(node->val);
return;
}
visited.insert(node);
findChildrenAtDistance(node->left, K - 1, result, visited);
findChildrenAtDistance(node->right, K - 1, result, visited);
visited.erase(node);
}
bool findTargetAndParents(TreeNode* root, TreeNode* target, unordered_map<TreeNode*, TreeNode*>& parentMap) {
if (!root) return false;
if (root == target) return true;
parentMap[root->left] = root;
if (findTargetAndParents(root->left, target, parentMap)) return true;
parentMap[root->right] = root;
if (findTargetAndParents(root->right, target, parentMap)) return true;
return false;
}
vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
unordered_map<TreeNode*, TreeNode*> parentMap;
vector<int> result;
unordered_set<TreeNode*> visited;
findTargetAndParents(root, target, parentMap);
queue<pair<TreeNode*, int>> bfsQueue;
bfsQueue.push({target, 0});
visited.insert(target);
while (!bfsQueue.empty()) {
auto [node, dist] = bfsQueue.front(); bfsQueue.pop();
if (dist == K) result.push_back(node->val);
for (TreeNode* neighbor : {node->left, node->right, parentMap[node]}) {
if (neighbor && !visited.count(neighbor)) {
visited.insert(neighbor);
bfsQueue.push({neighbor, dist + 1});
}
}
}
return result;
}function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
var distanceK = function(root, target, K) {
const parentMap = new Map();
populateParentMap(root, null);
const result = [], visited = new Set();
dfs(target, K);
function populateParentMap(node, parent) {
if (node) {
parentMap.set(node, parent);
populateParentMap(node.left, node);
populateParentMap(node.right, node);
}
}
function dfs(node, K) {
if (!node || visited.has(node)) return;
visited.add(node);
if (K === 0) {
result.push(node.val);
return;
}
dfs(node.left, K - 1);
dfs(node.right, K - 1);
dfs(parentMap.get(node), K - 1);
}
return result;
};using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public IList<int> DistanceK(TreeNode root, TreeNode target, int K) {
var parentMap = new Dictionary<TreeNode,TreeNode>();
BuildParentMap(root, null, parentMap);
var result = new List<int>();
var visited = new HashSet<TreeNode>();
Dfs(target, K, null, visited, parentMap, result);
return result;
}
private void BuildParentMap(TreeNode node, TreeNode parent, Dictionary<TreeNode,TreeNode> parentMap) {
if (node != null) {
parentMap[node] = parent;
BuildParentMap(node.left, node, parentMap);
BuildParentMap(node.right, node, parentMap);
}
}
private void Dfs(TreeNode node, int K, TreeNode parent, HashSet<TreeNode> visited, Dictionary<TreeNode,TreeNode> parentMap, IList<int> result) {
if (node == null || visited.Contains(node)) return;
visited.Add(node);
if (K == 0) {
result.Add(node.val);
return;
}
if (node.left != parent) Dfs(node.left, K - 1, node, visited, parentMap, result);
if (node.right != parent) Dfs(node.right, K - 1, node, visited, parentMap, result);
TreeNode parentNode = parentMap[node];
if (parentNode != null && parentNode != parent) Dfs(parentNode, K - 1, node, visited, parentMap, result);
}
}This Python approach starts by creating a parent map during a DFS traversal. Commencing from the target node, it executes another DFS to locate all nodes at distance K, avoiding repeated visits via a set collection.
Time Complexity: O(N), requiring a full tree traversal. Space Complexity: O(N), for both the map and recursive call stack.
Approach 3: DFS + Hash Table
We first use DFS to traverse the entire tree and save each node's parent node in the hash table g.
Next, we use DFS again, starting from target, to search for nodes at a distance of k both upwards and downwards, and add them to the result array.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function distanceK(root: TreeNode | null, target: TreeNode | null, k: number): number[] {
const g = new Map<TreeNode, TreeNode | null>();
const ans: number[] = [];
const dfs = (node: TreeNode | null, fa: TreeNode | null) => {
if (!node) {
return;
}
g.set(node, fa);
dfs(node.left, node);
dfs(node.right, node);
};
const dfs2 = (node: TreeNode | null, fa: TreeNode | null, k: number) => {
if (!node) {
return;
}
if (k === 0) {
ans.push(node.val);
return;
}
for (const nxt of [node.left, node.right, g.get(node) || null]) {
if (nxt !== fa) {
dfs2(nxt, node, k - 1);
}
}
};
dfs(root, null);
dfs2(target, null, k);
return ans;
}func distanceK(root *TreeNode, target *TreeNode, k int) []int {
g := make(map[*TreeNode]*TreeNode)
ans := []int{}
var dfs func(node, fa *TreeNode)
dfs = func(node, fa *TreeNode) {
if node == nil {
return
}
g[node] = fa
dfs(node.Left, node)
dfs(node.Right, node)
}
var dfs2 func(node, fa *TreeNode, k int)
dfs2 = func(node, fa *TreeNode, k int) {
if node == nil {
return
}
if k == 0 {
ans = append(ans, node.Val)
return
}
for _, nxt := range []*TreeNode{node.Left, node.Right, g[node]} {
if nxt != fa {
dfs2(nxt, node, k-1)
}
}
}
dfs(root, nil)
dfs2(target, nil, k)
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) using Parent Map | Time Complexity: O(N), where N is the number of nodes, since all nodes might be visited. Space Complexity: O(N) for parent map and queue. |
| Depth-First Search (DFS) with Backtracking | Time Complexity: O(N), requiring a full tree traversal. Space Complexity: O(N), for both the map and recursive call stack. |
| DFS + Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS with Parent Map | O(n) | O(n) | General case. Easiest to reason about when treating the tree as an undirected graph. |
| DFS with Backtracking | O(n) | O(h) | When minimizing extra memory and demonstrating deeper recursion-based reasoning. |
Frequently asked questions
Is All Nodes Distance K in Binary Tree easy or hard?
All Nodes Distance K in Binary Tree is classified as a Medium difficulty problem. The core challenge is recognizing that traversal must go both downward and upward from the target. Once the tree is treated like an undirected graph, a standard BFS level traversal solves it efficiently.
How to solve All Nodes Distance K in Binary Tree in O(n)?
Traverse the tree once to record parent pointers for every node. Then perform a BFS starting from the target node while expanding to its left child, right child, and parent. Track visited nodes to avoid cycles and stop when the BFS level equals k. The nodes in that level form the result, giving an overall O(n) solution.
All Nodes Distance K in Binary Tree Python or Java solution
In Python or Java, the typical implementation builds a HashMap or dictionary mapping each node to its parent, then runs a BFS using a queue starting from the target node. Each BFS level represents one edge distance. Once the level equals k, collect the node values and return them.
What is the best approach for All Nodes Distance K in Binary Tree?
The most common solution uses Breadth-First Search with a parent map. First build a mapping from each node to its parent, then start a BFS from the target node and explore left, right, and parent neighbors. When the BFS reaches distance k, all nodes at that level are the answer. This approach runs in O(n) time and O(n) space.
What data structure is used in All Nodes Distance K in Binary Tree?
The common solution uses a hash map to store parent pointers and a queue for Breadth-First Search. A visited set prevents revisiting nodes when moving between parent and child links. The alternative DFS solution relies on recursion and distance propagation during backtracking.
What is the time complexity of All Nodes Distance K in Binary Tree?
The optimal solutions run in O(n) time where n is the number of nodes in the tree. Each node is visited at most once either during the parent map construction or the traversal that finds nodes at distance k. Space complexity is O(n) for the BFS approach or O(h) for the DFS backtracking approach, where h is the tree height.
Is All Nodes Distance K in Binary Tree asked at Google Amazon or Meta?
This problem is a classic binary tree traversal question frequently asked in technical interviews at large companies including Google, Amazon, and Meta. It tests understanding of tree traversal, BFS levels, and how to convert a tree into a graph-like structure using parent references.