All Nodes Distance K in Binary Tree

Med

#0817Time: O(N), where N is the number of nodes in the tree. The `findParents` traversal takes O(N) time. The BFS also visits each node and edge at most once, which takes O(N) time.Space: O(N), where N is the number of nodes in the tree. The `parentMap` can store up to N-1 entries. The `visited` set can store up to N nodes. The `queue` in the worst case (a complete binary tree) can hold up to N/2 nodes. Thus, the space complexity is dominated by these data structures.7 companies

Algorithms

Depth-First Search Breadth-First Search

Data structures

Hash Table Tree Binary Tree

Companies

Flipkart Nutanix Samsung Walmart Labs

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach transforms the tree traversal problem into a graph traversal problem. Since a standard binary tree only allows downward traversal (from parent to child), we first need a way to traverse upwards. We can achieve this by creating a mapping from each node to its parent. Once we have this parent mapping, we can treat the tree as an undirected graph and perform a Breadth-First Search (BFS) starting from the target node to find all nodes at exactly distance k.

Algorithm

Step 1: Annotate Parents & Find Target.
1. Create a Map<TreeNode, TreeNode> parentMap.
2. Traverse the tree using DFS (or BFS). For each node, store its parent in the map: parentMap.put(node, parent).
Step 2: BFS from Target.
1. Initialize a Queue<TreeNode> queue and a Set<TreeNode> visited.
2. Add the target node to both the queue and the visited set.
3. Initialize distance = 0.
4. Loop while the queue is not empty: a. If distance == k, stop the loop. The nodes currently in the queue are part of the answer. b. Get the number of nodes at the current level: levelSize = queue.size(). c. Process all nodes at the current level: For i from 0 to levelSize - 1: i. Dequeue currentNode. ii. For each neighbor of currentNode (left child, right child, and parent from parentMap): - If the neighbor exists and has not been visited, add it to the queue and the visited set. d. Increment distance.
Step 3: Collect Results.
1. After the loop terminates, drain the queue and add the value of each node to a result list.
2. Return the result list.

Walkthrough

The method involves two main phases. First, we traverse the entire tree to build a data structure, typically a HashMap, that maps each node to its parent. This allows us to move upwards in the tree, which is not possible by default. During this initial traversal, we can also locate the target node.

Once we have the parent pointers and the target node, we start a Breadth-First Search (BFS) from the target. BFS is ideal for finding the shortest path in an unweighted graph, which is what our tree has become. We use a queue to manage the nodes to visit and a set to keep track of visited nodes to prevent cycles (e.g., moving from a child to its parent and back). The BFS proceeds in levels, where each level corresponds to an increase in distance from the target. We continue the BFS until we have reached level k. All nodes at this level are our answer.

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    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {12        Map<TreeNode, TreeNode> parentMap = new HashMap<>();13        findParents(root, null, parentMap);14 15        Queue<TreeNode> queue = new LinkedList<>();16        Set<TreeNode> visited = new HashSet<>();17        18        queue.offer(target);19        visited.add(target);20        21        int currentDistance = 0;22        23        while (!queue.isEmpty()) {24            if (currentDistance == k) {25                break;26            }27            int levelSize = queue.size();28            for (int i = 0; i < levelSize; i++) {29                TreeNode currentNode = queue.poll();30                31                // Add left child32                if (currentNode.left != null && !visited.contains(currentNode.left)) {33                    queue.offer(currentNode.left);34                    visited.add(currentNode.left);35                }36                37                // Add right child38                if (currentNode.right != null && !visited.contains(currentNode.right)) {39                    queue.offer(currentNode.right);40                    visited.add(currentNode.right);41                }42                43                // Add parent44                TreeNode parent = parentMap.get(currentNode);45                if (parent != null && !visited.contains(parent)) {46                    queue.offer(parent);47                    visited.add(parent);48                }49            }50            currentDistance++;51        }52        53        List<Integer> result = new ArrayList<>();54        while (!queue.isEmpty()) {55            result.add(queue.poll().val);56        }57        58        return result;59    }60 61    private void findParents(TreeNode node, TreeNode parent, Map<TreeNode, TreeNode> parentMap) {62        if (node == null) {63            return;64        }65        parentMap.put(node, parent);66        findParents(node.left, node, parentMap);67        findParents(node.right, node, parentMap);68    }69}

Complexity

Time

O(N), where N is the number of nodes in the tree. The `findParents` traversal takes O(N) time. The BFS also visits each node and edge at most once, which takes O(N) time.

Space

O(N), where N is the number of nodes in the tree. The `parentMap` can store up to N-1 entries. The `visited` set can store up to N nodes. The `queue` in the worst case (a complete binary tree) can hold up to N/2 nodes. Thus, the space complexity is dominated by these data structures.

Trade-offs

Pros

Conceptually simple and easy to understand if familiar with graph traversal algorithms like BFS.
Correctly handles all cases by converting the tree into a general graph.

Cons

Requires extra space proportional to the number of nodes (O(N)) for the parent map, visited set, and queue, which can be significant for large trees.

This approach avoids creating any auxiliary graph-like data structures (like a parent map or an adjacency list) and instead uses the call stack of a recursive Depth-First Search (DFS) to implicitly handle the upward traversal from the target node. It finds the nodes at distance k in a single pass over the tree.

Algorithm

Step 1: Main Recursive Function dfs(node, target, k)
1. Base Case: If node is null, return -1 (target not found).
2. Target Found: If node is the target, we must find all nodes in its own subtree at distance k. Call a helper findSubtreeNodes(node, k). Then, return 0 to signal the distance from the target to itself.
3. Recursive Step: Recursively call dfs on the left and right children. leftDist = dfs(node.left, ...) rightDist = dfs(node.right, ...)
Step 2: Process Distances and Propagate Upwards
1. Target in Left Subtree: If leftDist is not -1: a. The distance from the current node to the target is leftDist + 1. b. If this distance equals k, add node.val to the results. c. Search in the other (right) subtree for nodes. The required distance is k - (leftDist + 1) - 1. Call findSubtreeNodes(node.right, k - leftDist - 2). d. Return leftDist + 1 to the parent.
2. Target in Right Subtree: Perform a symmetric operation if rightDist is not -1.
3. Target Not Found: If both leftDist and rightDist are -1, return -1.
Step 3: Helper findSubtreeNodes(node, dist)
1. A simple DFS that collects all nodes at a specific depth dist from node.
2. Base Case: If node is null or dist < 0, return.
3. Distance Match: If dist == 0, add node.val to results.
4. Recurse: Call findSubtreeNodes on children with dist - 1.

Walkthrough

The core of this method is a recursive function, let's call it dfs, that traverses the tree and serves two purposes. First, it searches for the target node. Second, it uses its return value to communicate the distance from the current node to the target back up the call stack.

When the dfs function is at a given node:

If node is the target, it means we've found the starting point. We then trigger a separate downward search (findSubtreeNodes) from this target node to find all its descendants at distance k. The function returns 0 to its parent, indicating the distance.
If node is not the target, it recursively calls dfs on its children. If a recursive call (say, from the left child) returns a non-negative value d, it means the target is in the left subtree at a distance d from the left child. Therefore, the target is at distance d + 1 from the current node.
Now, from this current node, we know the path to the target goes through its left child. We check if the node itself is at distance k. We also need to find nodes in the other subtree (the right one) that are at the required distance. The path to these nodes goes up to the current node and then down into the right subtree. We can calculate the remaining distance and call findSubtreeNodes on the right child.

This process effectively explores all paths from the target: downwards into its own subtree, and upwards to each ancestor, branching off into the ancestor's other subtrees.

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    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {13        result = new ArrayList<>();14        dfs(root, target, k);15        return result;16    }17 18    // Returns the distance from node to target.19    // Returns -1 if target is not in the subtree of node.20    private int dfs(TreeNode node, TreeNode target, int k) {21        if (node == null) {22            return -1;23        }24 25        if (node == target) {26            // Found the target node. Now find all nodes in its subtree at distance k.27            findSubtreeNodes(node, k);28            return 0; // Distance from target to itself is 0.29        }30 31        // Recurse on left subtree32        int leftDist = dfs(node.left, target, k);33        if (leftDist != -1) {34            // Target is in the left subtree35            int distFromNodeToTarget = leftDist + 1;36            if (distFromNodeToTarget == k) {37                result.add(node.val);38            }39            // Search in the right subtree for nodes at the required distance40            findSubtreeNodes(node.right, k - distFromNodeToTarget - 1);41            return distFromNodeToTarget;42        }43 44        // Recurse on right subtree45        int rightDist = dfs(node.right, target, k);46        if (rightDist != -1) {47            // Target is in the right subtree48            int distFromNodeToTarget = rightDist + 1;49            if (distFromNodeToTarget == k) {50                result.add(node.val);51            }52            // Search in the left subtree for nodes at the required distance53            findSubtreeNodes(node.left, k - distFromNodeToTarget - 1);54            return distFromNodeToTarget;55        }56 57        return -1; // Target not found in this subtree58    }59 60    // Helper to find nodes in the subtree of 'node' at a specific distance 'dist'61    private void findSubtreeNodes(TreeNode node, int dist) {62        if (node == null || dist < 0) {63            return;64        }65        if (dist == 0) {66            result.add(node.val);67            return;68        }69        findSubtreeNodes(node.left, dist - 1);70        findSubtreeNodes(node.right, dist - 1);71    }72}

Complexity

Time

O(N), where N is the number of nodes. Each node is visited a constant number of times. The main `dfs` function and the helper `findSubtreeNodes` together ensure that every node is processed at most twice.

Space

O(H), where H is the height of the tree. This space is used by the recursion call stack. In the worst case of a skewed tree, H can be N, making the space complexity O(N). However, for a balanced tree, H is O(log N), making this approach significantly more space-efficient.

Trade-offs

Pros

More space-efficient than the graph-based approach, especially for balanced trees, as its space complexity is tied to the tree's height.
Solves the problem in a single pass without needing to pre-process the tree to build parent pointers or an adjacency list.

Cons

The recursive logic can be more complex to reason about compared to the straightforward graph traversal.
In the worst-case (a skewed tree), the space complexity is still O(N) due to the recursion depth.

Solutions

Solution

1/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { private Map < TreeNode , TreeNode > p ; private Set < Integer > vis ; private List < Integer > ans ; public List < Integer > distanceK ( TreeNode root , TreeNode target , int k ) { p = new HashMap <>(); vis = new HashSet <>(); ans = new ArrayList <>(); parents ( root , null ); dfs ( target , k ); return ans ; } private void parents ( TreeNode root , TreeNode prev ) { if ( root == null ) { return ; } p . put ( root , prev ); parents ( root . left , root ); parents ( root . right , root ); } private void dfs ( TreeNode root , int k ) { if ( root == null || vis . contains ( root . val )) { return ; } vis . add ( root . val ); if ( k == 0 ) { ans . add ( root . val ); return ; } dfs ( root . left , k - 1 ); dfs ( root . right , k - 1 ); dfs ( p . get ( root ), k - 1 ); } }

1/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: unordered_map < TreeNode * , TreeNode *> p ; unordered_set < int > vis ; vector < int > ans ; vector < int > distanceK ( TreeNode * root , TreeNode * target , int k ) { parents ( root , nullptr ); dfs ( target , k ); return ans ; } void parents ( TreeNode * root , TreeNode * prev ) { if ( ! root ) return ; p [ root ] = prev ; parents ( root -> left , root ); parents ( root -> right , root ); } void dfs ( TreeNode * root , int k ) { if ( ! root || vis . count ( root -> val )) return ; vis . insert ( root -> val ); if ( k == 0 ) { ans . push_back ( root -> val ); return ; } dfs ( root -> left , k - 1 ); dfs ( root -> right , k - 1 ); dfs ( p [ root ], k - 1 ); } };

1# 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 ]: def parents ( root , prev ): nonlocal p if root is None : return p [ root ] = prev parents ( root . left , root ) parents ( root . right , root ) def dfs ( root , k ): nonlocal ans , vis if root is None or root . val in vis : return vis . add ( root . val ) if k == 0 : ans . append ( root . val ) return dfs ( root . left , k - 1 ) dfs ( root . right , k - 1 ) dfs ( p [ root ], k - 1 ) p = {} parents ( root , None ) ans = [] vis = set () dfs ( target , k ) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem