All Nodes at Distance K Python Solution

In this tutorial, we will solve a problem on Binary Tree data structure. The problem statement is that if we are provided with the root node of the binary tree, the target node, and the distance value k, we need to return the list of all the values present at distance k from the target node in the given binary tree.

Consider the tree:

Look at the tree diagram above

Input: target = Node object with value 2.

root = Node object pointing to 1.

k = 2.

Output: [8, 9, 3]

If the target node is 4 and k is equal to 4, then the output

will be [6, 7]

Approach - 1

The main trick in this question is that we have to do more than traverse from top to bottom. We need two kinds of pointers. These are:

1. The first type of pointer is the one which will point toward the child nodes of the target node. For instance, if our target node is 2 and the value of k is 2, then the child nodes are 4 and 5.
2. The second pointer is the one that will point toward the parent node of the target node. For example, if the target node is 2, this pointer will point toward the parent node, 1.

The first pointer is the regular pointer present in the structure of the binary tree. However, the second kind of pointer is not available to us. Hence, we need to create this pointer.

Once we get both pointers, we must traverse the nodes starting from the target nodes. We will traverse in the radially outward direction from the target node, and on the completion of each traversal, we will decrement k by 1.

But the main question is how to get the nodes attached to the parent node of the target node. We have to traverse through the nodes that are not a part of the subtrees of the target node. For every node present in the upper tree, we will find the distance of that node from the target node, let this distance be dist, and now we will traverse through the other subtree of the nodes present in the upper tree and store all the nodes present at k - dist distance from the ancestor node.

Below is the code of the above approach:

Code

Output:

4
1
2

Time Complexity: This algorithm has the worst-case time complexity of O(N). The time complexity is not more than linear because no node in this algorithm is traversed more than once.

Space Complexity: This program has O(h) space complexity. Here h is the height of the given binary tree.

Approach - 2

This approach is more straightforward than the previous approach.

• We will first traverse the complete binary tree and get the path of the nodes from the root node. We will store this path in a list.
• In the next step, we will iterate through the list, and for every ith element of the path list, we will iterate and print the nodes present at the (k - i)th distance.

Code

Output:

[4, 1]

Time complexity: O(n)