All Nodes Distance K in Binary Tree

LeetCode 893 | Difficulty: Medium

Medium

Problem Description

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`

Topics: Hash Table, Tree, Depth-First Search, Breadth-First Search, Binary Tree

---

Approach

Tree DFS

Traverse the tree recursively (or with a stack). At each node, decide: what information do I need from the left/right subtrees? Process: go left → go right → combine results. Consider preorder, inorder, or postorder traversal based on when you need to process the node.

When to use

Path problems, subtree properties, tree structure manipulation.

Tree BFS (Level-Order)

Use a queue to process the tree level by level. At each level, process all nodes in the queue, then add their children. Track the level size to know when one level ends and the next begins.

When to use

Level-order traversal, level-based aggregation, right/left side view.

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

---

Solutions

Solution 1: C# (Best: 192 ms)

Metric	Value
Runtime	192 ms
Memory	40.3 MB
Date	2022-01-13

Solution

/**
 * Definition for a binary tree node.
 * 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 graph = new Dictionary<TreeNode, List<TreeNode>>();
    List<int> result = new List<int>();
    ConvertToGraph(root, graph);
    var visited = new HashSet<TreeNode>();
    var queue = new Queue<TreeNode>();
    visited.Add(target);
    queue.Enqueue(target);
    int depth = 0;
    while(queue.Count != 0)
    {
        var count = queue.Count;
        for (int i = 0; i < count; i++)
        {
            var current = queue.Dequeue();
            if(depth == k)
            result.Add(current.val);
            foreach (var neighbor in graph[current])
            {
                if(visited.Contains(neighbor)) continue;
                queue.Enqueue(neighbor);
                visited.Add(neighbor);              
            }
        }
        if(++depth > k) break;
    }
    return result;
}



private void ConvertToGraph(TreeNode root, Dictionary<TreeNode, List<TreeNode>> graph)
{
    if(root == null) return;
    if(!graph.ContainsKey(root)) graph.Add(root, new List<TreeNode>());
    if(root.left != null)
    {
        graph[root].Add(root.left);
        if(!graph.ContainsKey(root.left)) graph.Add(root.left,new List<TreeNode>());
        graph[root.left].Add(root);
        ConvertToGraph(root.left, graph);
    }

    if (root.right != null)
    {
        graph[root].Add(root.right);
        if (!graph.ContainsKey(root.right)) graph.Add(root.right, new List<TreeNode>());
        graph[root.right].Add(root);
        ConvertToGraph(root.right, graph);
    }
}
}

---

Complexity Analysis

Approach	Time	Space
Tree Traversal	$O(n)$	$O(h)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Consider: "What information do I need from each subtree?" — this defines your recursive return value.
• Hash map gives O(1) lookup — think about what to use as key vs value.