As the problem states that the distance can be upwards and downwards . So we considering both the case . I am going to implement BFS to implement it (Because requires the poped elements to trace back to the Source node to check whether path is sorted)
Consider the tree Given in this link .. I am taking tht as reference . http://en.wikipedia.org/wiki/Binary_tree Suppose the Source node is the left node of the root node . naming the nodes from A to I breadthwise . a(2)b(7)c(5)d(2)e(6)f(9)g(5)h(11)i(4) Case 1:- Traving from the root we note the distance from the Root to the source node but don't push it in the queue. Source node - b , Distance =3 ------------------------------------------------------------------- Queue = b | d e | g h Distance = 0 | 1 1 | 2 2 PrevNode = --| b b | e e So we don't get any distance as 3 . Leave this and reinitialize the Queue , Distance and PrevNode . Case 2 :-Any now Repeat this process from Root node to the source node to see whether we get the Distance as 3 . Case 3:- If the distance from the Root to the Source node is less than 'K' distance , then repeat the BFS process from the Root . Source node - b , Distance =3 ------------------------------------------------------------------- Queue = a | c | f | I Distance = 0 | 1 | 2 | 3 PrevNode = --| a | c | f Now the distance from the Root to the source node(d) is 1 here , s o we need to search for the node whose distance from the root is (K-d) . Here we will find the path with K=3 distance from the source node , But it will not be valid because it is not sorted .. So no node present will be printed . Hope I am clear . -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
