All Nodes Distance K in Binary Tree - Practice Coding Problems

All Nodes Distance K in Binary Tree - Problem

Imagine you're standing at a specific node in a binary tree and need to find all nodes that are exactly k steps away from your current position. You can move to parent nodes, left children, or right children - each move counts as one step.

Given the root of a binary tree, a target node value, and an integer k, return an array containing the values of all nodes that are exactly distance k from the target node.

The beauty of this problem is that distance can be measured in any direction - up to parents or down to children!

Example: If target node has value 5 and k=2, you need to find all nodes that require exactly 2 steps to reach from node 5, whether going through parents, children, or a combination of both.

Input & Output

example_1.py — Basic Tree

$ Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2

› Output: [7,4,1]

💡 Note: Nodes at distance 2 from target node 5 are: 7 (5→6→7), 4 (5→2→4), and 1 (5→3→1). The path can go through parents or children.

example_2.py — Single Node

$ Input: root = [1], target = 1, k = 3

› Output: []

💡 Note: There are no nodes at distance 3 from the target node 1, since the tree only has one node.

example_3.py — Distance 0

$ Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 0

› Output: [5]

💡 Note: At distance 0 from target node 5, only the target node itself qualifies.

Constraints

The number of nodes in the tree is in the range [1, 500]
0 ≤ Node.val ≤ 500
All values Node.val are unique
target is the value of one of the nodes in the tree
0 ≤ k ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Build the Network

Create parent-child connections so every node knows its neighbors

Start Spreading

Begin BFS from target node, like ripples in a pond

Level-by-Level

Each BFS level represents one more step of distance

Collect Results

After k levels, collect all nodes in the current BFS queue

Key Takeaway

🎯 Key Insight: Trees are just restricted graphs. Add parent pointers to enable bidirectional BFS, then distance k becomes k levels of BFS expansion.

Asked in

f Facebook 85 a Amazon 72 G Google 68 ⊞ Microsoft 45 Apple 32

The optimal solution uses parent mapping + BFS to convert the tree into an undirected graph, then performs level-order traversal from the target node. Key insight: distance in trees requires bidirectional navigation - we need parent pointers to traverse upward, combined with normal child pointers for downward traversal. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Parent Mapping + BFS	O(n)	O(n)	First pass builds parent-child mapping, second pass uses BFS from target
DFS with Parent Pointers (Optimal)	O(n)	O(n)	Single DFS pass builds graph and performs distance search simultaneously
Brute Force (DFS from Every Node)	O(n²)	O(h)	For each node, calculate distance to target and collect nodes at distance k

Parent Mapping + BFS — Algorithm Steps

First pass: Build parent mapping using DFS to connect each node to its parent
Create adjacency representation where each node knows its parent and children
Second pass: Use BFS starting from target node
Expand level by level until reaching distance k, then collect all nodes

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Parent Map

First pass creates bidirectional connections

Start BFS

Begin BFS from target node

Expand Level by Level

BFS explores neighbors at each distance level

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

#define MAX_NODES 1000

struct ParentMap {
    struct TreeNode* child;
    struct TreeNode* parent;
};

struct ParentMap parentMap[MAX_NODES];
int parentMapSize = 0;

struct TreeNode* findParent(struct TreeNode* node) {
    for (int i = 0; i < parentMapSize; i++) {
        if (parentMap[i].child == node) {
            return parentMap[i].parent;
        }
    }
    return NULL;
}

void addParentMap(struct TreeNode* child, struct TreeNode* parent) {
    parentMap[parentMapSize].child = child;
    parentMap[parentMapSize].parent = parent;
    parentMapSize++;
}

void buildParentMap(struct TreeNode* node, struct TreeNode* parent) {
    if (!node) return;
    addParentMap(node, parent);
    buildParentMap(node->left, node);
    buildParentMap(node->right, node);
}

int* distanceK(struct TreeNode* root, struct TreeNode* target, int k, int* returnSize) {
    *returnSize = 0;
    if (!root) return NULL;
    
    parentMapSize = 0;
    buildParentMap(root, NULL);
    
    struct TreeNode* queue[MAX_NODES];
    int visited[MAX_NODES] = {0};
    int front = 0, rear = 0;
    int* result = (int*)malloc(MAX_NODES * sizeof(int));
    
    queue[rear++] = target;
    // Mark target as visited (simplified)
    
    int distance = 0;
    while (front < rear) {
        if (distance == k) {
            while (front < rear) {
                result[(*returnSize)++] = queue[front++]->val;
            }
            break;
        }
        
        int size = rear - front;
        for (int i = 0; i < size; i++) {
            struct TreeNode* node = queue[front++];
            
            struct TreeNode* neighbors[3] = {findParent(node), node->left, node->right};
            for (int j = 0; j < 3; j++) {
                if (neighbors[j]) {
                    // Simplified visited check
                    queue[rear++] = neighbors[j];
                }
            }
        }
        distance++;
    }
    
    return result;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

First pass O(n) to build parent map, second pass O(n) for BFS in worst case

✓ Linear Growth

Space Complexity

O(n)

Parent hashmap stores O(n) relationships plus BFS queue space

⚡ Linearithmic Space

425.6K Views

High Frequency

~18 min Avg. Time

8.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Parent Mapping + BFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler