Domain 2MediumMEDIUM

All Nodes Distance K in Binary Tree

LeetCode problem 863: All Nodes Distance K in Binary Tree (medium).

Domain: medium•Updated: 2026-09-02
#Tree#Depth-first Search#Breadth-first Search

Problem Breakdown

Goal: Identify all nodes in a binary tree that are exactly K edges away from a specific target node.
Inputs:

  • root: The root of the binary tree (TreeNode).
  • target: A reference to an existing node within this tree (TreeNode).
  • K: An integer representing the distance (number of hops).

Outputs:

  • A list containing the .val integers of all nodes satisfying the condition. Order does not matter.

Constraints & Edge Cases:

  1. Unique Values: Node values are unique, which simplifies mapping if needed.
  2. Non-empty Tree: The tree always has at least one node (the root).
  3. Target Validity: target is guaranteed to be a valid node within the tree structure provided by root.
  4. Distance K=0: Should return only the target’s value itself.
  5. Traversal Direction: The challenge lies in moving up from the target towards ancestors and then down into their other subtrees, which standard DFS/BFS (which are directed downwards) do not handle natively without parent pointers or an explicit graph structure.

Intuition

A naive approach would be to run a BFS starting at target. However, since we only have access to .left and .right, we cannot traverse upwards towards the root from any node in this standard binary tree representation.

Brute Force: If we simply search for nodes by traversing down from every ancestor of the target (finding path length), it becomes complex because K can be reached via a sibling’s subtree or an uncle’s branch, not just direct descendants. A simple DFS/BFS starting at root won’t work efficiently without knowing where to stop relative to target.

Key Insight: To move “up” and then “down”, we must treat the binary tree as an undirected graph (or a network) where every node knows its neighbors: left child, right child, AND parent. Since standard TreeNode objects don’t store parents explicitly, we need to construct this connectivity information first or handle it implicitly during traversal.

Optimal Strategy:

  1. Establish Connectivity: Traverse the tree (e.g., via DFS) starting from root and record a mapping of each node’s value/pointer to its parent pointer logic (or build an adjacency list). This effectively converts our directed binary tree into a bidirectional graph structure in memory.
  2. BFS Search: Once we have this “parent” capability, run a standard BFS starting specifically from the target node with depth limit K. We use a visited set to prevent cycles (going back up immediately) and stop when distance exceeds K.

Approach

  1. Build Parent Map / Graph Structure: Perform a DFS traversal starting at root. For every child encountered, record its parent reference in a dictionary (parent_map). This allows us to traverse upwards from any node later. Note: Since we need neighbors for BFS (left, right, and up), storing just parents is sufficient if combined with existing .left/.right, but conceptually it’s easier to think of an adjacency list where neighbors[u] = [u.left, u.right, parent_of_u].
  2. BFS from Target: Initialize a queue with the target node and distance 0.
  3. Traversal Loop: While processing nodes:
    • If current depth equals K, add .val to results.
    • Add all valid neighbors (left, right, parent) that haven’t been visited yet to the queue with incremented depth.
  4. Termination: Stop when distance exceeds K.

Complexity Analysis

  • Time: O(N)O(N) where NN is the number of nodes in the tree. We traverse every node once during the initial parent-mapping phase, and then visit at most all reachable nodes within depth KK (bounded by total nodes) during BFS. In worst case (K≥N/2K \ge N/2), we touch almost all nodes again.
  • Space: O(N)O(N) to store the parent_map or adjacency list structure required for upward traversal, plus recursion stack space and queue storage for BFS.

Solution

from collections import deque
from typing import List

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def distanceK(root: 'TreeNode', target: 'TreeNode', K: int) -> List[int]:
    # Step 1: Build a parent map to enable upward traversal.
    # We use a dictionary mapping node value (or object if unique IDs used, 
    # but here we store Node->Parent logic implicitly via dict of nodes).
    # Since standard TreeNode doesn't have 'parent', we build this explicitly.
    
    # Using a set for visited in BFS later to avoid cycles back up/down immediately
    parent_map = {} 
    
    def dfs_build_parents(node):
        if not node: return None
        
        # If left child exists, record its parent as current node
        if node.left:
            parent_map[node.left] = node
        if node.right:
            parent_map[node.right] = node
            
        # Recurse to build for subtrees
        dfs_build_parents(node.left)
        dfs_build_parents(node.right)

    # Build the connectivity map (parent pointers stored in dict)
    dfs_build_parents(root)
    
    # Step 2: BFS from target with depth K
    queue = deque([(target, 0)])
    visited = {target}
    result = []
    
    while queue:
        node, dist = queue.popleft()
        
        if dist == K:
            result.append(node.val)
            
        # If we haven't reached distance K yet, explore neighbors
        if dist < K:
            for neighbor in [node.left, node.right]:
                if neighbor and neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, dist + 1))
            
            # Explore parent (upward movement enabled by map logic conceptually 
            # but here we need to access it. Since dfs_build_parents stored parents?
            # Wait, my dict above stores child -> node(parent). I can look up target's parent.)
            if node in parent_map:
                p = parent_map[node]
                if p not in visited:
                    visited.add(p)
                    queue.append((p, dist + 1))

    return result

Edge Cases Handled

  • K=0: The BFS loop checks dist == K immediately. Only the target node is added to results before exploring neighbors (since condition prevents adding if dist < K). Correctly returns [target.val].
  • Target at Root/Leaf: Logic holds regardless of position; parent map handles root’s lack of parent gracefully, and leaf nodes handle missing children via if neighbor checks.
  • Tree Depth < K + 1: BFS queue naturally empties or stops adding when neighbors are exhausted without reaching depth K (though problem implies valid tree structure). If path is shorter than K in a specific branch, those branches simply don’t contribute to result list for that distance level.