Print All The Nodes Which are X distance from the Given Node

Objec­tive: - Given Binary Tree, Print All The Nodes Which are X dis­tance from the Given Node.

Exam­ple :

Print-All-The-Nodes-Which-are-X-distance-from-the-Given-Node

Appraoch:

Quite Tricky solu­tion, i will explain using the exam­ple given in the pic­ture.
Find out all the nodes which are at dis­tance ‘3’ from the given node 5.

1. Find the height of the given node 5 is –3. say x = 3.
2. For all the nodes which are at dis­tance 3 and exist below node 5, con­sider 5 as root node and prob­lem will reduce to “Print all the nodes which are at dis­tance x from the root”. Agree?.
3. 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.
4. So now con­sider node 2 as root and again prob­lem will reduce to, Print all the nodes which are at dis­tance 2 from the root. remem­ber one thing when con­sid­er­ing the node 2 as root, you dont check the direc­tion of node 5 .(Why,?? because if you check nodes at dis­tance 2 from node 2, you will get 9, 7. Node 9 is at dis­tance 3 from Node 5 which is right but Node 7 is at dis­tance 1 from Node 5 which is wrong.)
5. How would you stop your pro­gram to check in the direc­tion of Node 5, when you go one level up, means at Node 2, after pro­cess­ing the 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.
6. Now recur­siv­ley go one more level up, now x = x-1 = 2–1 =1. It will be Node 1, con­sider Node 1 as root and again prob­lem will reduce to, Print all the nodes which are at dis­tance 1 from the root and don’t check the direc­tion of Node 2, with the same logic explained earlier.

Print-All-The-Nodes-Which-are-X-distance-from-the-Given-Node-Implementation.1

Com­plete Code:

Out­put:

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