All Nodes Distance K in Binary Tree

Identifying Problem Isomorphism

“All Nodes Distance K in Binary Tree” asks you to find all nodes that are K distance from a given target node in a binary tree. The problem is a combination of depth-first search (DFS) and breadth-first search (BFS) in a tree.

A simpler problem is “Minimum Depth of Binary Tree”. This problem requires you to find the minimum depth of a binary tree, which can be solved by BFS or DFS.

“All Nodes Distance K in Binary Tree” has an approximate isomorphic problem “Find All The Lonely Nodes”. In this problem, you need to find all nodes that have only one child node, which requires traversal and node inspection similar to the original problem but the criteria for selecting nodes is different.

A more complex problem related to “All Nodes Distance K in Binary Tree” is “Count Good Nodes in Binary Tree”. In this problem, you have to traverse the binary tree and count the number of ‘good’ nodes. A node is called good if the path from the root to that node includes no node greater than that node.

In ascending order of complexity, these problems could be arranged as:

  1. “Minimum Depth of Binary Tree” - Find the minimum depth of a binary tree.
  2. “All Nodes Distance K in Binary Tree” - Find all nodes at a certain distance from a target node in a binary tree.
  3. “Find All The Lonely Nodes” - Find nodes that have only one child in a binary tree.
  4. “Count Good Nodes in Binary Tree” - Count the number of ‘good’ nodes in a binary tree, where the path from the root to that node has no node greater than that node.

10 Prerequisite LeetCode Problems

863 involves tree traversal, depth-first search (DFS), breadth-first search (BFS), and potentially converting a tree to a graph, consider the following problems:

  1. 102. Binary Tree Level Order Traversal: This problem introduces the basic concept of BFS, which is key to problem 863.

  2. 101. Symmetric Tree: This problem helps you understand how to traverse a tree in a particular order, which is important for DFS and BFS.

  3. 133. Clone Graph: In this problem, you can practice BFS on a graph.

  4. 104. Maximum Depth of Binary Tree: This problem allows you to practice DFS on a binary tree.

  5. 105. Construct Binary Tree from Preorder and Inorder Traversal: Here, you’ll gain more experience with tree construction and traversal.

  6. 116. Populating Next Right Pointers in Each Node: This problem is a good practice for BFS and tree manipulation.

  7. 199. Binary Tree Right Side View: This is another BFS problem but requires some manipulation to get the right side view.

  8. 200. Number of Islands: Although this is not a tree problem, it helps to understand BFS and DFS in a matrix, which can be seen as a special kind of graph.

  9. 429. N-ary Tree Level Order Traversal: This problem extends the BFS concept to trees that have more than two children.

  10. 210. Course Schedule II: This problem provides practice for DFS on a graph.

The problem requires you to return all nodes in a binary tree that are a certain distance away from a given target node. Here’s a Python solution using Depth-First Search (DFS) and a dictionary to keep track of parent nodes:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

# 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]:
        # Define a dictionary to keep track of parent nodes
        parent = {root: None}

        # DFS function to populate the dictionary
        def dfs(node):
            for child in (node.left, node.right):
                if child:
                    parent[child] = node
                    dfs(child)

        dfs(root)

        # Define a list to keep track of visited nodes and a queue for BFS
        visited = {target}
        queue = collections.deque([(target, 0)])

        # BFS to find nodes K distance away
        while queue:
            node, dist = queue.popleft()

            if dist == k:
                return [x.val for x, d in queue] + [node.val]

            for nei in (node.left, node.right, parent[node]):
                if nei and nei not in visited:
                    visited.add(nei)
                    queue.append((nei, dist + 1))

        return []

This solution works by first doing a DFS to record each node’s parent, then doing a Breadth-First Search (BFS) from the target node to find all nodes a distance K away. If the distance from the target node equals K, it stops the BFS and returns the current node values. The time complexity is O(N) for traversing the tree, where N is the number of nodes in the tree, and the space complexity is also O(N) for storing the parent and visited information.

First Mark Parents and than from the target node go to left ,right and parent and decrease your target

Yes, you’re exactly right. The process involves a two-step approach:

  1. Mark Parents: First, we conduct a depth-first search (DFS) to populate a dictionary with all parent-child relationships in the tree. This will allow us to navigate upwards (towards the root) from any node.

  2. Explore Neighbors: Starting from the target node, we recursively explore all neighboring nodes (i.e., left child, right child, and parent), reducing our distance k by one at each level. This way, we can easily find all nodes at a specific distance from our target.

Python code illustrating this strategy:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, K: int) -> List[int]:
        # Define a dictionary to keep track of parent nodes
        parent = {root: None}
        
        # DFS function to populate the dictionary
        def dfs(node):
            for child in (node.left, node.right):
                if child:
                    parent[child] = node
                    dfs(child)

        # Begin DFS
        dfs(root)

        # Function to find nodes at distance K
        def find_nodes(node, prev, K, result):
            if node is None:
                return
            elif K == 0:
                result.append(node.val)
            else:
                # Explore left and right children
                if node.left != prev:
                    find_nodes(node.left, node, K-1, result)
                if node.right != prev:
                    find_nodes(node.right, node, K-1, result)
                # Explore parent
                if parent[node] != prev:
                    find_nodes(parent[node], node, K-1, result)

        # Initialize result list and call function
        result = []
        find_nodes(target, None, K, result)
        
        return result

In this code, find_nodes is a recursive function that explores neighboring nodes at a distance of K from the target node. The prev parameter is used to prevent the function from revisiting the node from which it just came. When the distance K reaches zero, we’ve found a node at the correct distance, and we append its value to our result list.

The time complexity of this approach is O(N), where N is the number of nodes in the tree, as in the worst-case scenario, we need to visit all nodes. The space complexity is also O(N), for storing the parent-child relationships and the recursive call stack.

Using BFS :- 1 Make the parent and current node map to traverse upwards. 2 We will do a BFS traversal starting from the target node until we reach the Kth level 3 Using BFS will check left, right child and also parent of current node. 4 when reached Kth distance, break out of BFS loop and remaining node’s values in our queue is our result. 5 Will take all the element from queue and add to our list as our answer.

Yes, your approach is also correct. The breadth-first search (BFS) algorithm is another common approach to solving this problem. Here is a Python code snippet illustrating your BFS approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

from collections import deque, defaultdict

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, K: int) -> List[int]:
        # Define a dictionary to keep track of parent nodes
        parent = defaultdict(list)
        
        # DFS function to populate the dictionary
        def dfs(node):
            if node:
                if node.left:
                    parent[node.val].append(node.left.val)
                    parent[node.left.val].append(node.val)
                    dfs(node.left)
                if node.right:
                    parent[node.val].append(node.right.val)
                    parent[node.right.val].append(node.val)
                    dfs(node.right)

        # Begin DFS
        dfs(root)

        # Begin BFS
        queue = deque([(target.val, 0)])
        seen = {target.val}
        while queue:
            node, dist = queue.popleft()
            if dist == K:
                return [n for n, _ in queue] + [node]
            for nei in parent[node]:
                if nei not in seen:
                    seen.add(nei)
                    queue.append((nei, dist+1))

        return []

This BFS approach uses a queue to iteratively visit all neighbors (left, right, and parent) of each node, keeping track of the distance from the target node. If a node’s distance equals K, it’s added to the result list. The BFS continues until all nodes have been visited or the distance equals K. The use of BFS ensures that nodes are visited in increasing order of distance from the target node.

The time complexity is O(N), where N is the number of nodes in the tree, as each node needs to be visited once. The space complexity is also O(N) for storing the parent-child relationships, the visited set, and the queue.

We cannot go back in a tree, but we can go anywhere in a graph. If we construct a graph according to the tree, that would be much easier to handle.

Absolutely, your approach is correct! We can indeed convert the tree into an undirected graph and then traverse it to find nodes at a distance K from the target node.

We would first do a depth-first search (DFS) on the tree to convert it into a graph where every node points to its adjacent nodes including its parent and children. Then we can perform a breadth-first search (BFS) from the target node to find all nodes at a distance K.

Here is a Python code snippet that demonstrates this approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

from collections import defaultdict, deque

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, K: int) -> List[int]:
        # Build graph
        graph = defaultdict(list)
        def dfs(node, parent=None):
            if node:
                if parent:
                    graph[parent.val].append(node.val)
                    graph[node.val].append(parent.val)
                dfs(node.left, node)
                dfs(node.right, node)
                
        dfs(root)

        # BFS
        queue = deque([(target.val, 0)])
        seen = {target.val}
        while queue:
            node, dist = queue.popleft()
            if dist == K:
                return [node] + [n for n, _ in queue]
            for nei in graph[node]:
                if nei not in seen:
                    seen.add(nei)
                    queue.append((nei, dist + 1))
        return []

In the code snippet above, the function dfs is used to convert the tree into an undirected graph where each node has references to its parent and children. After the graph is constructed, we perform BFS starting from the target node and maintain a queue of nodes to be explored along with their corresponding distances from the target node. If we encounter a node at distance K, we return it and all remaining nodes in the queue as the answer.

The time complexity for this approach is O(N), where N is the number of nodes in the tree, and the space complexity is also O(N), where the space is used to store the graph and the queue.

You have to handle the parent node. It is a problem for graph!

Yes, you’re correct. Since we’ve converted the tree to a graph, which means a node’s parent is now one of its “children”, we must be careful not to “go back” to the parent node while performing the breadth-first search (BFS). This would essentially be moving backwards towards the root, away from the nodes that are K distance away from the target node.

One way to handle this is to keep track of the nodes that we’ve already visited while performing the BFS, and then avoid revisiting these nodes. This can be done using a set in Python, for instance, where we add nodes as we visit them and then skip nodes that are already in the set.

The updated BFS part in Python would look like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# BFS
queue = deque([(target.val, 0)])
visited = set([target.val])
while queue:
    node, dist = queue.popleft()
    if dist == K:
        return [node] + [n for n, _ in queue]
    for nei in graph[node]:
        if nei not in visited:
            visited.add(nei)
            queue.append((nei, dist + 1))
return []

In this version, visited is a set that stores the nodes we’ve visited. Before we add a node’s neighbor to the queue, we first check if it’s in visited, and skip it if it is.

Traverse all nodes and record parent node using dfs and then using bfs find all nodes of k length.

Yes, exactly!

Your approach combines DFS (Depth-First Search) and BFS (Breadth-First Search) to solve this problem efficiently.

Here is how you can do it:

  1. First, use DFS to traverse the tree and create a dictionary where the key is a node, and the value is its parent node.
1
2
3
4
5

def dfs(node, parent):
    if node:
        parent_node[node] = parent
        dfs(node.left, node)
        dfs(node.right, node)
  1. Then, use BFS to find all nodes at distance K from the target node. Keep track of visited nodes to avoid circles.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def bfs(target, K):
    queue = deque([(target, 0)])
    visited = {target}
    while queue:
        if queue[0][1] == K:
            return [node.val for node, _ in queue]
        node, dist = queue.popleft()
        for neighbor in (node.left, node.right, parent_node[node]):
            if neighbor and neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    return []
  1. Finally, call dfs to create the parent node dictionary, and bfs to find the nodes at distance K.
1
2
3

parent_node = {root: None}
dfs(root, None)
return bfs(target, K)

This approach uses DFS to pre-process the tree and BFS to find the answer, taking advantage of the strengths of both algorithms. It’s a common pattern in tree and graph problems and a good technique to have in your toolkit.

I’m confused about the meaning of distance

In Testcase 1: I just modify k = 3 and think “2” will be the answer of one because we can go through the path (5->2->5->2), but the answer is not. is distance contains “shortest” meaning in CS?

In the context of tree or graph traversal in computer science, “distance” typically refers to the shortest path between two nodes.

In your example, if you modify k to 3, the node with value “2” won’t be included in the answer because the shortest path from “5” to “2” is of length 1 (5 -> 2), not 3. When you think of the path as (5 -> 2 -> 5 -> 2), you’re not considering the shortest path, you’re making a round trip, which doesn’t align with the concept of distance in this context.

So, in the problem you’re trying to solve, the distance is indeed referring to the shortest path from the target node to all other nodes. And nodes at distance k from the target node means there are k edges between the target node and these nodes in the shortest path.

This understanding is fundamental when solving problems related to tree or graph traversal and shortest paths.

As a tip, when you’re asked for nodes at a distance k from a target node, it’s often helpful to visualize the problem in terms of layers or concentric circles emanating from the target node. The nodes at a distance k will be on the kth layer or circle.

Is 2385. Amount of Time for Binary Tree to Be Infected similar to All Nodes Distance K in Binary Tree?

On the surface, the problem “2385. Amount of Time for Binary Tree to Be Infected” might seem similar to “863. All Nodes Distance K in Binary Tree”. Both of them involve propagating some form of information or state through a tree. However, the specific details, constraints, and objectives of the two problems are quite different.

In “863. All Nodes Distance K in Binary Tree”, you are given a specific node (the ’target’) and you must find all nodes that are a certain distance from that node. This problem is essentially asking for you to do a breadth-first or depth-first traversal of the tree from the target node, but also keep track of the distance from the target node to each node you visit.

On the other hand, “2385. Amount of Time for Binary Tree to Be Infected” would involve a different kind of propagation. You would likely need to simulate or calculate the propagation of the infection through the tree over time, which might involve different kinds of tree traversal or dynamic programming.

So, while they may seem similar due to both involving propagation through a tree, the details of what you are propagating and how you need to propagate it differ significantly between the two problems. Therefore, the methods and algorithms used to solve them might also be quite different.

can some tell me how this tree will be constructed : [0,1,null,null,2,null,3,null,4] target 3 k =1

transform the given binary tree into an equivalent graph, where each pointer is treated as an undirected edge. Hence, the graph retains all the connected nodes from the original binary tree, including the pointers from children to parents. Consequently, we can perform a regular search in this graph, starting with depth-first search algorithm as an example.In the equivalent graph, we only need to recursively visit all unvisited neighboring nodes of the current node, which include nodes that are equivalent to the left and right children and the parent in the original tree.

Similarly, we can use a hash set to keep track of all the visited nodes. Whenever we find an unvisited neighbor node, we add it to the hash set so it won’t be visited anymore.

Let me break it down into simpler terms:

  1. Transformation into a graph: In a binary tree, each node has up to two “children” nodes (left and right) and one “parent” node. However, in a traditional tree structure, there is no way to go back from a child node to its parent node because it’s a unidirectional structure - you can only go from parent to child.

    Now, imagine if we could create “links” from each child node back to its parent node, thus making it a two-way street. This would mean you could traverse the structure not only from parent to child but also from child to parent. This effectively transforms our binary tree into a graph where each edge (link) is undirected, meaning you can move freely in both directions.

  2. DFS on the graph: Once our binary tree has been converted into a graph, we can apply search algorithms used on graphs, such as Depth-First Search (DFS). DFS explores as far as possible along each branch before backtracking. In our case, DFS would start at the target node and explore all of its neighboring nodes (left, right, and parent nodes).

  3. Visited Nodes: To prevent DFS from visiting a node more than once (which could lead to infinite loops in cases where nodes are closely connected), we use a hash set (or any other data structure) to keep track of all nodes that have been visited. Before we visit a new node, we would check if it is in our set of visited nodes. If it’s there, we skip it; if it isn’t, we add it to our set and continue our DFS from that node.

This is the basic idea behind the approach you described. It allows you to perform a search on a binary tree similar to how you would on a graph, enabling you to effectively find all nodes at a certain distance from a given node.

we start with the node target with distance = 0, then we mark all its unvisited neighbor nodes with distance = 1 to be visited soon, once we visit a node with distance = 1, we mark all its unvisited neighbor nodes with distance = 2 as well.

We can use a queue queue as a container to store all nodes to be visited without mixing the order. Since the operation on the queue is done in First In, First Out (FIFO) order, it allows us to explore all nodes with the current distance to the target node, before moving on to the nodes with larger distances.Similarly, we use a hash set to keep track of all the visited nodes. Whenever we find an unvisited neighbor node, we add it to the hash set so it won’t be visited anymore.

Let’s break it down:

  1. Initial Node (target): The process starts at the ’target’ node. The distance from the target to itself is 0, so we consider this our starting point.

  2. Neighbor Nodes with distance=1: Next, we look at the ’target’ node’s immediate neighbors in the graph. These nodes are one step or “distance=1” away from the target. However, we don’t visit these neighbors yet. Instead, we mark them to be visited soon.

  3. Adding to the Queue: We use a queue, a kind of data structure where elements are kept in order and removed in the order they were added (First In, First Out). We add all these neighbors that we’ve marked to be visited to our queue.

  4. Visit Nodes in the Queue: Now we start visiting the nodes in our queue, starting with the nodes at “distance=1”. We go to each neighbor and then look at their neighbors. These “neighbors of neighbors” are at “distance=2” from our original target node.

  5. Mark New Neighbors: Just like before, we don’t visit these “distance=2” nodes yet, but instead add them to our queue to be visited next.

  6. Visited Nodes: To make sure we don’t visit the same node multiple times (which would be a waste of time), we keep track of all the nodes we’ve already visited in a hash set. Before visiting a node, we check if it’s in our set. If it is, we skip it. If it’s not, we add it to our set and continue the process from step 4.

This process is repeated, each time visiting nodes that are one step further away from the target than the last batch we visited. This ensures that we visit all nodes at “distance=1” before “distance=2”, all nodes at “distance=2” before “distance=3”, and so on, until we’ve visited all the nodes we need to. This is why it’s called a Breadth-First Search (BFS) – we explore the breadth (neighbors) of our graph before moving onto the next layer of nodes.

The first solution modifies the existing tree to add parent links, while the second and third solutions re-create a graph containing both parent and child links. An intermediate (and IMHO cleaner) solution is to just supplement the existing tree structure with a hash map that identifies a parent node for each node value.

Yes, you’re correct. Let’s discuss this intermediate approach for the problem of finding all nodes at distance k from a target node in a binary tree.

In a typical binary tree node, we have two references: left and right, pointing to the left child and right child respectively. We don’t have a direct reference to the parent node.

  1. Creating Parent Links with a HashMap: Here, the idea is to supplement the binary tree with a HashMap that will map each node value to its parent node. We can easily construct this HashMap using a pre-order traversal on the given binary tree. During the traversal, when we’re at a node, we can get its left child and right child. Since we are at the parent, we can add a mapping from child -> parent in our HashMap.

  2. BFS for Finding Nodes at Distance K: With this HashMap, we effectively have a graph representation of our binary tree where we can navigate up to parent or down to children. Now we can perform a Breadth-First Search starting from the target node. The BFS will allow us to navigate the tree level by level away from the target node, stopping when we’ve reached the required distance k. This BFS will need to check at each step if it’s visiting a node for the second time to avoid cycles, which is where our HashMap of visited nodes will come in handy.

By using this intermediate approach, you’re avoiding the modification of the existing tree structure, and also preventing the need to completely recreate the graph, which could be a cleaner and more efficient solution depending on the circumstances.

Let’s break down that function call:

graph.computeIfAbsent(cur.val, k -> new ArrayList<>()).add(parent.val);

In Java, computeIfAbsent is a function provided by the Map interface. The method attempts to compute a mapping for the specified key and its current mapped value (or null if there is no current mapping).

cur.val is the key being looked up in the Map called graph.

k -> new ArrayList<>() is a lambda function that gets called if cur.val is not currently in graph. This function takes an input k (which would be cur.val), but ignores it and just returns a new ArrayList.

So, what computeIfAbsent does in this context is check if cur.val is a key in graph. If it isn’t, it puts cur.val into graph with a new ArrayList as its value. Either way, it then returns the ArrayList that cur.val maps to.

After the computeIfAbsent call, we are guaranteed to have an ArrayList that cur.val maps to. We then call add(parent.val) on that ArrayList, which adds the parent value to the ArrayList.

In summary, this line of code is building an adjacency list representation of a graph, where each node’s value maps to a list of its adjacent nodes’ values. This is done by ensuring that an ArrayList exists for cur.val, then adding parent.val to that ArrayList.

You can rebuild the tree and root it at target, then just run 1 dfs to find the answer.

Yes, that is one possible solution. You could modify the tree to make the target node the new root. In this new tree, any node’s value represents its distance from the target. Then, you would perform a depth-first search (DFS) to find all nodes that are a distance k from the root (the target).

Here are the general steps to follow for this approach:

  1. First, use DFS to find the target node from the given root and, at the same time, build a parent map that you can use to navigate upwards in the tree.

  2. Modify the tree to make the target node the new root. In this new tree, the value of each node represents its distance from the target. During this process, you would disconnect the original parent of the target (to prevent cycles) and then traverse the rest of the tree (using both the left, right, and parent pointers) to update the remaining nodes.

  3. Perform another DFS on the modified tree, adding the value of any node that has a distance of k from the root to your result list.

This approach ensures that you visit each node only once, so the time complexity is O(N), where N is the number of nodes in the tree. The space complexity is also O(N), to store the parent map and the output list.

Remember to always carefully analyze the given problem and the proposed solution, as different problems may require different approaches. While the steps outlined above work well for this problem, it may not be the optimal solution for other, similar problems.

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