Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

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

    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

You may also like...