# Leetcode – 863. All Nodes Distance K In Binary Tree

When I first saw this problem, I panicked! I knew that this some how had to be a Breadth First Search problem because BFS from any node gives you the shortest path to every other node that is connected to the tree. Since every node is represented as a `TreeNode` with only `left` and `right` pointers, I would need to know the parent too for me to do a BFS from the target node and that was the reason for my panic. In fact, I even started doing a dry run of a Floyd-Warshall algorithm as this algorithm gives the shortest path between all pairs of nodes in a graph in `O(N^3)` time.

Depth First Search to the rescue! I later realized that I can use DFS to generate a map of a node to it’s parent and at this point, I should stop looking at the tree as a tree but as a graph.

For example, given the tree:

For `target = 5` and `K = 2`, we need to return `[7, 4, 1]`. Once we have performed DFS and generated the map, we should now start looking at this tree as a graph as such:

Now, we can perform BFS from the target node and whenever we encounter a node which is `K` distance away, we can append it to our results array. We can even have an optimization to break the BFS loop when we encounter a node at distance greater than `K` as BFS guarantees that we will process all nodes at a distance `d` before going to distance `d + 1`.

The code for this problem is as follows:

The time complexity of this problem is `O(N)` for DFS and `O(N)` for BFS which gives us a total of `O(N)`.

The space complexity is `O(lg N)` for the DFS recursive stack and `O(N)` for the BFS queue which gives us a total of `O(N)`.

Problem taken from Leetcode.

Solution hosted on Github.

Leetcode – 863. All Nodes Distance K In Binary Tree

This site uses Akismet to reduce spam. Learn how your comment data is processed.