Be the first user to complete this post

82. Find Nodes at Distance X from a Given Node in a Tree

Objective: - Given Binary Tree, Print All The Nodes That are X distance from the Given Node.

Example :

Approach:

Let's discuss the solution from an example (See the image below)
Find out all the nodes that are at a distance '3' from the given node 5.

Find the height of the given node 5, which is 3. say x = 3.
For all the nodes that are at distance 3 and exist below node 5, consider 5 as the root node and the problem will reduce to Print all the nodes that are at distance x from the root. Agree?.
But what about the other nodes, go one level up ( at the path from root to node 5), which is node 2. Since you have gone up by one level, x will be x = x-1 = 3-1 = 2.
So now consider node 2 as the root and again the problem will be reduced to, Print all the nodes which are at distance 2 from the root. remember one thing when considering node 2 as root, you don't check the direction of node 5 . (Why,?? because if you check nodes at distance 2 from node 2, you will get 9 and 7. Node 9 is at distance 3 from Node 5 which is right but Node 7 is at distance 1 from Node 5 which is wrong.)
How would you stop your program from checking in the direction of Node 5, when you go one level up, means at Node 2, after processing Node 5, return Node 5 to Node 2, and at Node 2 check whether Node 5 is right child or left child of Node 2, based on that don't check that direction.
Now recursively go one more level up, now x = x-1 = 2-1 =1. It will be Node 1, consider Node 1 as the root, and again the problem will be reduced to, Print all the nodes that are at distance 1 from the root and don't check the direction of Node 2, with the same logic explained earlier.

Output:

Nodes at distance '3' from Node '5' are : 11 9 3