Leetcode – 863. All Nodes Distance K In Binary Tree

Reading Time: 2 minutes

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.

Mohit AthwaniLeetcode – 863. All Nodes Distance K In Binary Tree

Leave a Reply

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