LeetCode Problem 863

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

Solution

LeetCode 863 - All Nodes Distance K in Binary Tree

Problem Understanding

This problem gives us the root of a binary tree, a specific target node inside that tree, and an integer k. Our task is to return all node values whose distance from the target node is exactly k.

The important detail is the definition of distance. The distance between two nodes is the number of edges in the shortest path connecting them. In a binary tree, we usually move downward from parent to child, but distance calculations may require moving upward as well. For example, a node that is k steps away from the target could be:

• In the target's left subtree
• In the target's right subtree
• Above the target through parent links
• In a sibling subtree reached by going upward first

This means the tree effectively behaves like an undirected graph when solving this problem.

The input consists of:

• root, the root node of the binary tree
• target, a reference to one node in the tree
• k, the required distance

The output should be a list of node values whose shortest path distance from target equals k. The order does not matter.

The constraints are relatively small:

• At most 500 nodes
• Node values are unique
• k can be as large as 1000

The uniqueness of node values is helpful because it allows us to identify nodes clearly. The small tree size means multiple approaches are possible, but we still want an efficient and clean solution.

Several edge cases are important:

• k = 0, where the answer should simply be the target node itself
• A single-node tree
• k larger than the height of the tree, which should return an empty list
• The target being the root node
• The target being a leaf node
• Nodes that are reachable only by moving upward before moving downward again

A naive implementation that only searches downward from the target would fail because valid nodes may exist through parent paths.

Approaches

Brute Force Approach

A brute-force solution would treat every node in the tree as a candidate answer.

For each node:

1. Compute the distance from that node to the target
2. If the distance equals k, include it in the result

To compute distances, we could repeatedly search the tree for paths between nodes. One common brute-force method is:

• For every node, run a DFS from the root to find the path to the target
• Run another DFS to find the path to the current node
• Compare the paths to compute the distance

This works because the distance between two nodes can be derived from their lowest common ancestor.

However, this is inefficient. If there are n nodes and each distance computation takes O(n), the total complexity becomes O(n²).

Although n <= 500 is manageable, this approach is unnecessarily expensive and complicated.

Optimal Approach

The key insight is that distance problems in trees become much easier if we can move both downward and upward.

A normal binary tree node only contains references to its children. It does not contain a pointer to its parent. Therefore, we first transform the tree into an undirected graph structure by recording parent relationships.

Once every node knows its parent, each node can move in three directions:

• Left child
• Right child
• Parent

At that point, the problem becomes a standard breadth-first search problem:

• Start BFS from the target node
• Expand level by level
• After exactly k levels, all nodes currently in the queue are the answer

BFS is ideal because it naturally explores nodes in increasing order of distance.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly computes distances between nodes
Optimal	O(n)	O(n)	Uses parent mapping and BFS from target

Algorithm Walkthrough

Step 1: Build Parent References

Traverse the tree using DFS or BFS and store each node's parent in a hash map.

We use a hash map because tree nodes do not naturally contain parent pointers. This allows constant-time access to a node's parent during traversal.

For example:

parent[5] = 3
parent[6] = 5
parent[2] = 5

The root node has no parent.

Step 2: Initialize BFS from the Target Node

Create a queue for BFS and insert the target node.

Also create a visited set to prevent revisiting nodes. This is critical because once parent links are added, the tree behaves like an undirected graph, and cycles become possible.

Without a visited set, traversal could bounce endlessly between parent and child.

Step 3: Process BFS Level by Level

Each BFS level represents nodes at a certain distance from the target.

For every node removed from the queue:

• Explore its left child
• Explore its right child
• Explore its parent

Any unvisited neighbor is added to the queue.

After processing one full level, increment the current distance.

Step 4: Stop When Distance Equals k

Once the BFS depth reaches k, every node currently in the queue is exactly distance k away from the target.

Extract their values and return them.

Why it works

Breadth-first search guarantees that nodes are explored in order of increasing distance from the starting node. Since we transformed the tree into an undirected graph using parent references, BFS explores every reachable node exactly once. Therefore, when BFS reaches level k, all nodes in that level are precisely distance k from the target.

Python Solution

from collections import deque
from typing import List, Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def distanceK(
        self,
        root: TreeNode,
        target: TreeNode,
        k: int
    ) -> List[int]:

        parent_map = {}

        def build_parent_map(node: Optional[TreeNode], parent: Optional[TreeNode]) -> None:
            if not node:
                return

            parent_map[node] = parent

            build_parent_map(node.left, node)
            build_parent_map(node.right, node)

        build_parent_map(root, None)

        queue = deque([target])
        visited = {target}

        current_distance = 0

        while queue:
            if current_distance == k:
                return [node.val for node in queue]

            level_size = len(queue)

            for _ in range(level_size):
                current_node = queue.popleft()

                neighbors = [
                    current_node.left,
                    current_node.right,
                    parent_map[current_node]
                ]

                for neighbor in neighbors:
                    if neighbor and neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)

            current_distance += 1

        return []

The solution begins by constructing a parent map. This step converts the tree into a graph-like structure where each node can move both upward and downward.

The recursive helper function traverses the entire tree and records the parent of every node. The root maps to None because it has no parent.

Next, BFS begins from the target node. The queue stores nodes to process at the current distance level, while the visited set prevents revisiting nodes.

Inside the BFS loop, we first check whether the current level corresponds to distance k. If it does, every node currently in the queue belongs in the answer.

Otherwise, we process the entire level and expand outward by exploring all valid neighbors:

• Left child
• Right child
• Parent

After processing one level, the distance counter increases by one.

If BFS finishes without reaching distance k, the function returns an empty list.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func distanceK(root *TreeNode, target *TreeNode, k int) []int {
    parentMap := make(map[*TreeNode]*TreeNode)

    var buildParentMap func(node, parent *TreeNode)

    buildParentMap = func(node, parent *TreeNode) {
        if node == nil {
            return
        }

        parentMap[node] = parent

        buildParentMap(node.Left, node)
        buildParentMap(node.Right, node)
    }

    buildParentMap(root, nil)

    queue := []*TreeNode{target}
    visited := make(map[*TreeNode]bool)
    visited[target] = true

    currentDistance := 0

    for len(queue) > 0 {
        if currentDistance == k {
            result := []int{}

            for _, node := range queue {
                result = append(result, node.Val)
            }

            return result
        }

        levelSize := len(queue)

        for i := 0; i < levelSize; i++ {
            currentNode := queue[0]
            queue = queue[1:]

            neighbors := []*TreeNode{
                currentNode.Left,
                currentNode.Right,
                parentMap[currentNode],
            }

            for _, neighbor := range neighbors {
                if neighbor != nil && !visited[neighbor] {
                    visited[neighbor] = true
                    queue = append(queue, neighbor)
                }
            }
        }

        currentDistance++
    }

    return []int{}
}

The Go implementation follows the same algorithmic structure as the Python solution.

The parent relationships are stored using a map from node pointers to parent pointers. Since Go does not have Python's dynamic hashable objects, pointer references are used directly as map keys.

The BFS queue is implemented with a slice. Nodes are removed from the front using slicing operations.

The visited structure is a map[*TreeNode]bool, which efficiently tracks already processed nodes.

Nil checks are necessary before exploring neighbors because Go uses nil pointers instead of Python's None.

Worked Examples

Example 1

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

The tree structure is:

        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4

Step 1: Build Parent Map

Node	Parent
3	None
5	3
1	3
6	5
2	5
0	1
8	1
7	2
4	2

Step 2: Initialize BFS

Queue:

[5]

Visited:

{5}

Current distance:

0

Step 3: Process Distance 0

Remove node 5.

Neighbors:

• 6
• 2
• 3

Queue after processing:

[6, 2, 3]

Visited:

{5, 6, 2, 3}

Distance becomes 1.

Step 4: Process Distance 1

Process node 6:

• No new neighbors

Process node 2:

• Add 7
• Add 4

Process node 3:

• Add 1

Queue becomes:

[7, 4, 1]

Distance becomes 2.

Step 5: Stop

Current distance equals k.

Return:

[7, 4, 1]

Example 2

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

Step 1: Build Parent Map

Node	Parent
1	None

Step 2: Initialize BFS

Queue:

[1]

Distance:

0

Step 3: Process Node

Node 1 has no children and no parent.

Queue becomes empty.

Step 4: End BFS

No nodes exist at distance 3.

Return:

[]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited at most once during DFS and once during BFS
Space	O(n)	Parent map, visited set, and BFS queue may all store up to n nodes

The algorithm performs two traversals of the tree.

The first traversal builds the parent map, visiting every node exactly once. The second traversal performs BFS from the target node, again visiting each node at most once because of the visited set.

The auxiliary data structures all scale linearly with the number of nodes in the tree.

Test Cases

from collections import deque

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 = {}

        def build_parent_map(node, parent):
            if not node:
                return

            parent_map[node] = parent

            build_parent_map(node.left, node)
            build_parent_map(node.right, node)

        build_parent_map(root, None)

        queue = deque([target])
        visited = {target}

        current_distance = 0

        while queue:
            if current_distance == k:
                return [node.val for node in queue]

            for _ in range(len(queue)):
                current_node = queue.popleft()

                neighbors = [
                    current_node.left,
                    current_node.right,
                    parent_map[current_node]
                ]

                for neighbor in neighbors:
                    if neighbor and neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)

            current_distance += 1

        return []

solution = Solution()

# Example 1
root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
root.right.left = TreeNode(0)
root.right.right = TreeNode(8)
root.left.right.left = TreeNode(7)
root.left.right.right = TreeNode(4)

assert sorted(solution.distanceK(root, root.left, 2)) == [1, 4, 7]  # standard example

# Example 2
root2 = TreeNode(1)

assert solution.distanceK(root2, root2, 3) == []  # k larger than tree height

# k = 0
assert solution.distanceK(root2, root2, 0) == [1]  # target itself

# Target is root
assert sorted(solution.distanceK(root, root, 1)) == [1, 5]  # direct children

# Target is leaf node
assert sorted(solution.distanceK(root, root.left.left, 2)) == [2, 3]  # upward traversal required

# Large k
assert solution.distanceK(root, root.left, 10) == []  # no nodes at that distance

# One-sided tree
chain = TreeNode(1)
chain.right = TreeNode(2)
chain.right.right = TreeNode(3)
chain.right.right.right = TreeNode(4)

assert solution.distanceK(chain, chain.right, 2) == [4]  # linear chain traversal

# Distance through parent and sibling subtree
assert sorted(solution.distanceK(root, root.left.right, 2)) == [3, 6]  # mixed upward and downward traversal

Test Summary

Test	Why
Standard example tree	Validates the core BFS logic
Single-node tree with large k	Ensures empty result handling
k = 0	Confirms target node itself is returned
Target is root	Tests downward-only traversal
Target is leaf	Tests upward traversal through parents
Very large k	Ensures BFS terminates correctly
One-sided tree	Tests degenerate tree structure
Mixed traversal path	Validates graph-style movement

Edge Cases

Case 1: k = 0

When k equals zero, the correct answer is simply the target node itself because the distance from a node to itself is zero.

This can easily cause off-by-one errors if the BFS increments the distance counter incorrectly before checking the current level.

The implementation handles this correctly by checking:

if current_distance == k:

before processing the next BFS level.

Case 2: Target Node is a Leaf

A leaf node has no children, so a downward-only traversal would fail to find many valid answers.

For example, a node at distance 2 from a leaf may require:

• Moving upward to the parent
• Then downward into another subtree

The parent map solves this issue by allowing traversal in all directions.

Case 3: k Larger Than Tree Height

If k exceeds the maximum reachable distance from the target, no valid nodes exist.

A buggy implementation might continue indefinitely or return incorrect partial results.

This implementation naturally handles the situation because BFS eventually exhausts all reachable nodes. Once the queue becomes empty, the algorithm returns an empty list.

Case 4: Preventing Cycles

Once parent pointers are introduced, the structure behaves like an undirected graph.

For example:

5 <-> 3

Without a visited set, BFS could repeatedly move back and forth between connected nodes forever.

The visited set guarantees each node is processed at most once, preventing infinite loops and preserving the O(n) complexity.