Problem editorial

All Nodes Distance K in Binary Tree

MediumTree Traversal Patterns (DFS & BFS)Hash TableTreeDepth-First Search

Editorial

Core insight

All Nodes Distance K in Binary Tree · Tree Traversal Patterns (DFS & BFS)

Core Insight for All Nodes Distance K in Binary Tree

The core difficulty in LeetCode 863 is accessing the "parent" and the "sibling" subtrees, as standard tree nodes do not have parent pointers.

The key insight is that the recursion stack implicitly holds the path from the root to the current node. When we find the target node during a DFS traversal, the function call stack contains all the ancestors of target.

We can leverage this by designing a DFS function that returns the distance from the target to the current node.

If a node is the target, it returns distance 0.
If a node receives a valid distance from one of its children (meaning the target is in that child's subtree), the current node knows it is distance + 1 away from the target.
If a node is not the target and the target is not in its subtrees, it returns -1.

Visualizing the Data Flow: Imagine the recursion tree. We dive deep until we hit the target.

At the target: We immediately search its subtree (downwards) for nodes at distance k.
Returning (Unwinding): As the recursion returns to the parent of the target, the parent learns "My left child contains the target at distance 0." The parent is therefore at distance 1.
Crossing Over: Since the parent is at distance 1, it looks at its right child (the sibling of the target). It knows it needs to find nodes in that right subtree that are distance k - 1 - 1 (subtracting 1 for the parent-to-child edge) away.

This effectively allows us to treat the tree as a graph where we "radiate" outwards from the target, using the return values of the recursion to handle the upward movement.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 863: All Nodes Distance K in Binary Tree Solution & Explanation

Problem Overview

TL;DR: The optimal solution utilizes a recursive DFS (specifically postorder traversal logic) to locate the target node and propagate distances upward to ancestors, allowing us to traverse "down" into adjacent subtrees to find nodes at the correct distance.

The LeetCode 863 problem, "All Nodes Distance K in Binary Tree," asks us to find every node in a binary tree that is exactly k edges away from a specific target node. The output should be a list of values, and the order does not matter. Unlike a standard graph where edges are bidirectional by default, a binary tree node typically only points to its children. This makes traversing "up" toward the root to find distant nodes in other branches the primary challenge.

Brute Force Approach for All Nodes Distance K in Binary Tree

A naive or brute-force approach often attempts to treat the tree as a generic graph without optimizing for the tree's recursive structure.

One common brute-force method involves two distinct phases:

Graph Conversion: Traverse the entire tree to build an adjacency list (or map) where every node points to its parent and its children. This effectively converts the directed tree into an undirected graph.
Breadth-First Search (BFS): Perform a standard BFS starting from the target node using the adjacency list to find all nodes at layer k.

python

1# Pseudo-code for Brute Force (Graph Conversion)
2def brute_force(root, target, k):
3    graph = build_adjacency_list(root) # O(N) space and time
4    queue = [(target, 0)]
5    visited = {target}
6    result = []
7    
8    while queue:
9        node, dist = queue.pop(0)
10        if dist == k:
11            result.append(node.val)
12        if dist < k:
13            for neighbor in graph[node]:
14                if neighbor not in visited:
15                    visited.add(neighbor)
16                    queue.append((neighbor, dist + 1))
17    return result

Complexity Analysis:

Time Complexity: $O(N)$ , as we visit each node to build the graph and potentially visit each node again during BFS.
Space Complexity: $O(N)$ , required to store the adjacency list (parent pointers) and the BFS queue.

Why it is suboptimal: While the time complexity is technically linear, this approach requires $O(N)$ extra space to store the parent pointers or graph representation explicitly. It fails to utilize the implicit recursive stack that a Depth-First Search provides, which can solve the problem without allocating new data structures for the entire tree topology.

Algorithm Strategy: Tree DFS - Recursive Postorder Traversal

We will implement a primary DFS function that returns the distance from the target to the current node. We will also use a helper function (or logic) to collect nodes downwards.

Downwards Collection Helper: Create a helper function collect_k_down(node, d) that adds all nodes in the subtree of node at depth d to the result list. This is a standard DFS/preorder traversal.
Main DFS (Postorder Logic): Define a function find_target_dist(node):
- Base Case: If node is null, return -1.
- Target Case: If node is target:
  - Call collect_k_down(node, k) to find nodes in the target's own subtree.
  - Return 1 (indicating the parent is distance 1 away).
- Recursive Step:
  - Call left_dist = find_target_dist(node.left).
  - Call right_dist = find_target_dist(node.right).
- Processing Returns:
  - If left_dist is not -1 (Target is in left subtree):
    - Check if left_dist == k. If so, the current node is an answer.
    - Otherwise, call collect_k_down(node.right, k - left_dist - 1) to search the other side.
    - Return left_dist + 1.
  - If right_dist is not -1 (Target is in right subtree):
    - Check if right_dist == k. If so, the current node is an answer.
    - Otherwise, call collect_k_down(node.left, k - right_dist - 1) to search the other side.
    - Return right_dist + 1.
- Not Found: Return -1.

Execution Flow

Let's trace the algorithm with root = [3,5,1], target = 5, k = 1.

Start DFS at Root (3):
- Call find_target_dist(3).
Traverse Left to Node (5):
- Call find_target_dist(5).
- Node is target.
- Action: Call collect_k_down(5, 1). Finds children of 5 at distance 1. Adds them to result.
- Return: Returns 1 to parent (3).
Back at Root (3):
- left_dist is 1.
- Is left_dist == k (1 == 1)? Yes. Add 3 to result.
- Is left_dist < k? No, so we don't search the right subtree of 3.
- Return: Returns 2 (distance to parent of 3, if it existed).
Completion:
- The algorithm finishes. Result contains children of 5 and the node 3.

Proof of Correctness

The correctness relies on the invariant that find_target_dist(node) always returns the exact distance from node to target if target exists in node's subtree.

Case 1: Nodes in Target's Subtree. These are handled explicitly when node == target via the collect_k_down helper.
Case 2: Ancestors of Target. These are identified as the recursion unwinds. If a recursive call returns a non-negative value $d$ , the current node is an ancestor at distance $d$ .
Case 3: Nodes in Side Branches. For any ancestor at distance $d$ , the algorithm explicitly searches the opposite child for nodes at distance $k - d - 1$ . This covers all nodes reachable by going "up" then "down".

Since a tree has a unique path between any two nodes, covering these three regions ensures all nodes at distance k are found exactly once.

Pattern Reuse Notes

The Tree DFS - Recursive Postorder Traversal pattern is highly reusable. Mastering the "bottom-up" information flow allows you to solve several other popular interview questions:

LeetCode 104: Maximum Depth of Binary Tree - Uses postorder to pass heights up from children to calculate the max depth at the parent.
LeetCode 110: Balanced Binary Tree - Passes height information upwards while simultaneously checking the balance condition.
LeetCode 124: Binary Tree Maximum Path Sum - Similar to finding distance, this passes the "maximum gain" from subtrees upwards to compute the global maximum path.
LeetCode 145: Binary Tree Postorder Traversal - The foundational problem for this pattern, focusing purely on the traversal order.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 863

cpp

1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8 * };
9 */
10class Solution {
11public:
12    vector<int> result;
13
14    // Helper to find nodes at distance 'k' downwards from 'node'
15    void addSubtreeNodes(TreeNode* node, int k) {
16        if (!node || k < 0) return;
17        if (k == 0) {
18            result.push_back(node->val);
19            return;
20        }
21        addSubtreeNodes(node->left, k - 1);
22        addSubtreeNodes(node->right, k - 1);
23    }
24
25    // Returns distance from target if found in subtree, else -1
26    int dfs(TreeNode* node, TreeNode* target, int k) {
27        if (!node) return -1;
28
29        if (node == target) {
30            addSubtreeNodes(node, k);
31            return 1; // Distance from target to parent is 1
32        }
33
34        int leftDist = dfs(node->left, target, k);
35        if (leftDist != -1) {
36            if (leftDist == k) {
37                result.push_back(node->val);
38            } else {
39                // Target is in left, so search right for remaining distance
40                addSubtreeNodes(node->right, k - leftDist - 1);
41            }
42            return leftDist + 1;
43        }
44
45        int rightDist = dfs(node->right, target, k);
46        if (rightDist != -1) {
47            if (rightDist == k) {
48                result.push_back(node->val);
49            } else {
50                // Target is in right, so search left for remaining distance
51                addSubtreeNodes(node->left, k - rightDist - 1);
52            }
53            return rightDist + 1;
54        }
55
56        return -1;
57    }
58
59    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
60        result.clear();
61        dfs(root, target, k);
62        return result;
63    }
64};

Java Solution for LeetCode 863

java

1/**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 *     int val;
5 *     TreeNode left;
6 *     TreeNode right;
7 *     TreeNode(int x) { val = x; }
8 * }
9 */
10class Solution {
11    List<Integer> result;
12
13    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
14        result = new ArrayList<>();
15        findTargetAndPropagate(root, target, k);
16        return result;
17    }
18
19    // Returns distance to target. Returns -1 if target not found in subtree.
20    private int findTargetAndPropagate(TreeNode node, TreeNode target, int k) {
21        if (node == null) return -1;
22
23        if (node == target) {
24            addSubtreeNodes(node, k);
25            return 1; // Return 1 to indicate parent is distance 1 away
26        }
27
28        int leftDist = findTargetAndPropagate(node.left, target, k);
29        if (leftDist != -1) {
30            if (leftDist == k) {
31                result.add(node.val);
32            } else {
33                // Target is in left subtree, check right subtree
34                // Distance needed in right child: k - (distance to node) - 1 (edge to right child)
35                addSubtreeNodes(node.right, k - leftDist - 1);
36            }
37            return leftDist + 1;
38        }
39
40        int rightDist = findTargetAndPropagate(node.right, target, k);
41        if (rightDist != -1) {
42            if (rightDist == k) {
43                result.add(node.val);
44            } else {
45                // Target is in right subtree, check left subtree
46                addSubtreeNodes(node.left, k - rightDist - 1);
47            }
48            return rightDist + 1;
49        }
50
51        return -1;
52    }
53
54    // Standard DFS to add nodes at exactly distance 'dist'
55    private void addSubtreeNodes(TreeNode node, int dist) {
56        if (node == null || dist < 0) return;
57        if (dist == 0) {
58            result.add(node.val);
59            return;
60        }
61        addSubtreeNodes(node.left, dist - 1);
62        addSubtreeNodes(node.right, dist - 1);
63    }
64}

Python Solution for LeetCode 863

python

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, x):
4#         self.val = x
5#         self.left = None
6#         self.right = None
7
8class Solution:
9    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
10        result = []
11
12        # Helper to find nodes at specific distance downwards
13        def add_subtree_nodes(node, dist):
14            if not node or dist < 0:
15                return
16            if dist == 0:
17                result.append(node.val)
18                return
19            add_subtree_nodes(node.left, dist - 1)
20            add_subtree_nodes(node.right, dist - 1)
21
22        # Main DFS that returns distance from target
23        def dfs(node):
24            if not node:
25                return -1
26            
27            if node == target:
28                add_subtree_nodes(node, k)
29                return 1 # Parent is 1 away from target
30            
31            # Check left subtree
32            left_dist = dfs(node.left)
33            if left_dist != -1:
34                if left_dist == k:
35                    result.append(node.val)
36                else:
37                    # Target is in left, search right branch
38                    add_subtree_nodes(node.right, k - left_dist - 1)
39                return left_dist + 1
40            
41            # Check right subtree
42            right_dist = dfs(node.right)
43            if right_dist != -1:
44                if right_dist == k:
45                    result.append(node.val)
46                else:
47                    # Target is in right, search left branch
48                    add_subtree_nodes(node.left, k - right_dist - 1)
49                return right_dist + 1
50            
51            return -1
52
53        dfs(root)
54        return result

AI Coach Insight

For All Nodes Distance K in Binary Tree, focus on explaining why the structure works, not just naming Tree Traversal Patterns (DFS & BFS).

Complexity Analysis

Time Complexity: $O(N)$ $O (N)$
- We visit every node in the tree at most twice: once during the search for the target (main DFS) and potentially once more during the collect_k_down calls. Since the subtrees searched by collect_k_down are disjoint from the path to the target, the total operations remain linear with respect to the number of nodes $N$ .
Space Complexity: $O(H)$ $O (H)$
- $H$ is the height of the tree. This space is used by the recursion stack. In the worst case (skewed tree), $H = N$ . In a balanced tree, $H = \log N$ . We do not store an adjacency list, making this more space-efficient than the graph conversion approach.

Related Patterns

Pattern: Tree Traversal Patterns (DFS & BFS)
Subpattern: Tree DFS - Recursive Postorder Traversal

This problem fits the Tree DFS - Recursive Postorder Traversal subpattern because we need information from the children (specifically, "is the target in your subtree, and how far is it?") to be passed up to the parent. The parent then processes this information to decide whether to search its other child. This bottom-up information flow is the hallmark of postorder traversal.

Common Mistakes & FAQ

Why does the naive solution often TLE or run slow?
- Mistake: Converting the tree to a graph using an adjacency matrix or hash map of all nodes.
- Reasoning: While $O(N)$ time, the constant factors are high due to map hashing and memory allocation. It also demonstrates a lack of understanding of tree-specific recursion properties.
- Consequence: Higher memory usage and less impressive algorithmic intuition in interviews.
Why is my logic failing for ancestors?
- Mistake: Forgetting to subtract 1 when switching branches.
- Reasoning: If node is distance d from target, its other child is 1 edge away from node. Therefore, the distance remaining to search in that child's subtree is k - d - 1.
- Consequence: Off-by-one errors in the result set.
What happens if k=0?
- Mistake: The code assumes k > 0 and tries to access children or subtract from k.
- Reasoning: The base case in the addSubtree helper must handle k=0 immediately by adding the current node.
- Consequence: Missing the target node itself in the output, or crashing on null pointer checks.
Why do I need to return dist + 1?
- Mistake: Returning dist without incrementing.
- Reasoning: The return value represents the distance from the target to the current node. As we move up the stack to the parent, the distance increases by 1.
- Consequence: Distance calculations for ancestors will be incorrect (too small).

Practise All Nodes Distance K in Binary Tree and the problems around it

All Nodes Distance K in Binary Tree is a Tree Traversal Patterns (DFS & BFS) problem, in the Recursive Postorder Traversal subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Core insight

All Nodes Distance K in Binary Tree · Tree Traversal Patterns (DFS & BFS)

Core Insight for All Nodes Distance K in Binary Tree

The core difficulty in LeetCode 863 is accessing the "parent" and the "sibling" subtrees, as standard tree nodes do not have parent pointers.

We can leverage this by designing a DFS function that returns the distance from the target to the current node.

If a node is the target, it returns distance 0.
If a node receives a valid distance from one of its children (meaning the target is in that child's subtree), the current node knows it is distance + 1 away from the target.
If a node is not the target and the target is not in its subtrees, it returns -1.

Visualizing the Data Flow: Imagine the recursion tree. We dive deep until we hit the target.

At the target: We immediately search its subtree (downwards) for nodes at distance k.
Returning (Unwinding): As the recursion returns to the parent of the target, the parent learns "My left child contains the target at distance 0." The parent is therefore at distance 1.
Crossing Over: Since the parent is at distance 1, it looks at its right child (the sibling of the target). It knows it needs to find nodes in that right subtree that are distance k - 1 - 1 (subtracting 1 for the parent-to-child edge) away.

This effectively allows us to treat the tree as a graph where we "radiate" outwards from the target, using the return values of the recursion to handle the upward movement.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 863: All Nodes Distance K in Binary Tree Solution & Explanation

Problem Overview

Brute Force Approach for All Nodes Distance K in Binary Tree

A naive or brute-force approach often attempts to treat the tree as a generic graph without optimizing for the tree's recursive structure.

One common brute-force method involves two distinct phases:

Graph Conversion: Traverse the entire tree to build an adjacency list (or map) where every node points to its parent and its children. This effectively converts the directed tree into an undirected graph.
Breadth-First Search (BFS): Perform a standard BFS starting from the target node using the adjacency list to find all nodes at layer k.

python

1# Pseudo-code for Brute Force (Graph Conversion)
2def brute_force(root, target, k):
3    graph = build_adjacency_list(root) # O(N) space and time
4    queue = [(target, 0)]
5    visited = {target}
6    result = []
7    
8    while queue:
9        node, dist = queue.pop(0)
10        if dist == k:
11            result.append(node.val)
12        if dist < k:
13            for neighbor in graph[node]:
14                if neighbor not in visited:
15                    visited.add(neighbor)
16                    queue.append((neighbor, dist + 1))
17    return result

Complexity Analysis:

Time Complexity: $O(N)$ , as we visit each node to build the graph and potentially visit each node again during BFS.
Space Complexity: $O(N)$ , required to store the adjacency list (parent pointers) and the BFS queue.

Algorithm Strategy: Tree DFS - Recursive Postorder Traversal

We will implement a primary DFS function that returns the distance from the target to the current node. We will also use a helper function (or logic) to collect nodes downwards.

Downwards Collection Helper: Create a helper function collect_k_down(node, d) that adds all nodes in the subtree of node at depth d to the result list. This is a standard DFS/preorder traversal.
Main DFS (Postorder Logic): Define a function find_target_dist(node):
- Base Case: If node is null, return -1.
- Target Case: If node is target:
  - Call collect_k_down(node, k) to find nodes in the target's own subtree.
  - Return 1 (indicating the parent is distance 1 away).
- Recursive Step:
  - Call left_dist = find_target_dist(node.left).
  - Call right_dist = find_target_dist(node.right).
- Processing Returns:
  - If left_dist is not -1 (Target is in left subtree):
    - Check if left_dist == k. If so, the current node is an answer.
    - Otherwise, call collect_k_down(node.right, k - left_dist - 1) to search the other side.
    - Return left_dist + 1.
  - If right_dist is not -1 (Target is in right subtree):
    - Check if right_dist == k. If so, the current node is an answer.
    - Otherwise, call collect_k_down(node.left, k - right_dist - 1) to search the other side.
    - Return right_dist + 1.
- Not Found: Return -1.

Execution Flow

Let's trace the algorithm with root = [3,5,1], target = 5, k = 1.

Start DFS at Root (3):
- Call find_target_dist(3).
Traverse Left to Node (5):
- Call find_target_dist(5).
- Node is target.
- Action: Call collect_k_down(5, 1). Finds children of 5 at distance 1. Adds them to result.
- Return: Returns 1 to parent (3).
Back at Root (3):
- left_dist is 1.
- Is left_dist == k (1 == 1)? Yes. Add 3 to result.
- Is left_dist < k? No, so we don't search the right subtree of 3.
- Return: Returns 2 (distance to parent of 3, if it existed).
Completion:
- The algorithm finishes. Result contains children of 5 and the node 3.

Proof of Correctness

The correctness relies on the invariant that find_target_dist(node) always returns the exact distance from node to target if target exists in node's subtree.

Case 1: Nodes in Target's Subtree. These are handled explicitly when node == target via the collect_k_down helper.
Case 2: Ancestors of Target. These are identified as the recursion unwinds. If a recursive call returns a non-negative value $d$ , the current node is an ancestor at distance $d$ .
Case 3: Nodes in Side Branches. For any ancestor at distance $d$ , the algorithm explicitly searches the opposite child for nodes at distance $k - d - 1$ . This covers all nodes reachable by going "up" then "down".

Since a tree has a unique path between any two nodes, covering these three regions ensures all nodes at distance k are found exactly once.

Pattern Reuse Notes

The Tree DFS - Recursive Postorder Traversal pattern is highly reusable. Mastering the "bottom-up" information flow allows you to solve several other popular interview questions:

LeetCode 104: Maximum Depth of Binary Tree - Uses postorder to pass heights up from children to calculate the max depth at the parent.
LeetCode 110: Balanced Binary Tree - Passes height information upwards while simultaneously checking the balance condition.
LeetCode 124: Binary Tree Maximum Path Sum - Similar to finding distance, this passes the "maximum gain" from subtrees upwards to compute the global maximum path.
LeetCode 145: Binary Tree Postorder Traversal - The foundational problem for this pattern, focusing purely on the traversal order.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 863

cpp

1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8 * };
9 */
10class Solution {
11public:
12    vector<int> result;
13
14    // Helper to find nodes at distance 'k' downwards from 'node'
15    void addSubtreeNodes(TreeNode* node, int k) {
16        if (!node || k < 0) return;
17        if (k == 0) {
18            result.push_back(node->val);
19            return;
20        }
21        addSubtreeNodes(node->left, k - 1);
22        addSubtreeNodes(node->right, k - 1);
23    }
24
25    // Returns distance from target if found in subtree, else -1
26    int dfs(TreeNode* node, TreeNode* target, int k) {
27        if (!node) return -1;
28
29        if (node == target) {
30            addSubtreeNodes(node, k);
31            return 1; // Distance from target to parent is 1
32        }
33
34        int leftDist = dfs(node->left, target, k);
35        if (leftDist != -1) {
36            if (leftDist == k) {
37                result.push_back(node->val);
38            } else {
39                // Target is in left, so search right for remaining distance
40                addSubtreeNodes(node->right, k - leftDist - 1);
41            }
42            return leftDist + 1;
43        }
44
45        int rightDist = dfs(node->right, target, k);
46        if (rightDist != -1) {
47            if (rightDist == k) {
48                result.push_back(node->val);
49            } else {
50                // Target is in right, so search left for remaining distance
51                addSubtreeNodes(node->left, k - rightDist - 1);
52            }
53            return rightDist + 1;
54        }
55
56        return -1;
57    }
58
59    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
60        result.clear();
61        dfs(root, target, k);
62        return result;
63    }
64};

Java Solution for LeetCode 863

java

1/**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 *     int val;
5 *     TreeNode left;
6 *     TreeNode right;
7 *     TreeNode(int x) { val = x; }
8 * }
9 */
10class Solution {
11    List<Integer> result;
12
13    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
14        result = new ArrayList<>();
15        findTargetAndPropagate(root, target, k);
16        return result;
17    }
18
19    // Returns distance to target. Returns -1 if target not found in subtree.
20    private int findTargetAndPropagate(TreeNode node, TreeNode target, int k) {
21        if (node == null) return -1;
22
23        if (node == target) {
24            addSubtreeNodes(node, k);
25            return 1; // Return 1 to indicate parent is distance 1 away
26        }
27
28        int leftDist = findTargetAndPropagate(node.left, target, k);
29        if (leftDist != -1) {
30            if (leftDist == k) {
31                result.add(node.val);
32            } else {
33                // Target is in left subtree, check right subtree
34                // Distance needed in right child: k - (distance to node) - 1 (edge to right child)
35                addSubtreeNodes(node.right, k - leftDist - 1);
36            }
37            return leftDist + 1;
38        }
39
40        int rightDist = findTargetAndPropagate(node.right, target, k);
41        if (rightDist != -1) {
42            if (rightDist == k) {
43                result.add(node.val);
44            } else {
45                // Target is in right subtree, check left subtree
46                addSubtreeNodes(node.left, k - rightDist - 1);
47            }
48            return rightDist + 1;
49        }
50
51        return -1;
52    }
53
54    // Standard DFS to add nodes at exactly distance 'dist'
55    private void addSubtreeNodes(TreeNode node, int dist) {
56        if (node == null || dist < 0) return;
57        if (dist == 0) {
58            result.add(node.val);
59            return;
60        }
61        addSubtreeNodes(node.left, dist - 1);
62        addSubtreeNodes(node.right, dist - 1);
63    }
64}

Python Solution for LeetCode 863

python

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, x):
4#         self.val = x
5#         self.left = None
6#         self.right = None
7
8class Solution:
9    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
10        result = []
11
12        # Helper to find nodes at specific distance downwards
13        def add_subtree_nodes(node, dist):
14            if not node or dist < 0:
15                return
16            if dist == 0:
17                result.append(node.val)
18                return
19            add_subtree_nodes(node.left, dist - 1)
20            add_subtree_nodes(node.right, dist - 1)
21
22        # Main DFS that returns distance from target
23        def dfs(node):
24            if not node:
25                return -1
26            
27            if node == target:
28                add_subtree_nodes(node, k)
29                return 1 # Parent is 1 away from target
30            
31            # Check left subtree
32            left_dist = dfs(node.left)
33            if left_dist != -1:
34                if left_dist == k:
35                    result.append(node.val)
36                else:
37                    # Target is in left, search right branch
38                    add_subtree_nodes(node.right, k - left_dist - 1)
39                return left_dist + 1
40            
41            # Check right subtree
42            right_dist = dfs(node.right)
43            if right_dist != -1:
44                if right_dist == k:
45                    result.append(node.val)
46                else:
47                    # Target is in right, search left branch
48                    add_subtree_nodes(node.left, k - right_dist - 1)
49                return right_dist + 1
50            
51            return -1
52
53        dfs(root)
54        return result

All Nodes Distance K in Binary Tree

Core insight

Core Insight for All Nodes Distance K in Binary Tree

Full breakdown

LeetCode 863: All Nodes Distance K in Binary Tree Solution & Explanation

Problem Overview

Brute Force Approach for All Nodes Distance K in Binary Tree

Algorithm Strategy: Tree DFS - Recursive Postorder Traversal

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 863

Java Solution for LeetCode 863

Python Solution for LeetCode 863

Practise All Nodes Distance K in Binary Tree and the problems around it

Related problems

All Nodes Distance K in Binary Tree

Core insight

Core Insight for All Nodes Distance K in Binary Tree

Full breakdown

LeetCode 863: All Nodes Distance K in Binary Tree Solution & Explanation

Problem Overview

Brute Force Approach for All Nodes Distance K in Binary Tree

Algorithm Strategy: Tree DFS - Recursive Postorder Traversal

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 863

Java Solution for LeetCode 863

Python Solution for LeetCode 863

Practise All Nodes Distance K in Binary Tree and the problems around it

Related problems