My bad, I wrote "out degree" where I should have written "in degree". My proposal: Topological Sort <http://en.wikipedia.org/wiki/Topological_sorting> the graph and keep removing the nodes from vertices which have "in degree" of 0 (given the DAG, there will always be at least one such vertex). For a BST, since just root has an in degree of 0, start by removing the 2 out nodes from it. Now you will have 2 vertices with in degree as 0, repeat this for each of them. The last vertex which will be left i.e. the one without any out degree will be one end of your solution and the root will be the other. Essentially, for a BST this problem is equal to finding the depth of the tree.
Also I made a blunder by assuming the graph is directed (DAG). The question does not say graph is directed or undirected. This approach will work for DAG. For undirected, convert the graph in to a directed graph first and then start with the vertices whose in degree is 1. Veni Vedi Slumber ! On Fri, May 24, 2013 at 6:19 AM, MAC <macatad...@gmail.com> wrote: > kindly explain .... visualizing a balanced BST as a graph and unable to > underdstand your point > > > thanks > --mac > > > On Fri, May 24, 2013 at 6:04 AM, Avi Dullu <avi.du...@gmail.com> wrote: > >> >> On Sat, May 11, 2013 at 10:29 AM, Aman Jain <pureama...@gmail.com> wrote: >> >>> 2. from this no*de u*, again apply* dfs* to find longest distant node >>> from this node.Let us say that node is v. >>> >> >> Small doubt about the solution. Consider this graph a -> b -> c -> d >> >> You randomly choose vertex 'b' and do a DFS. Your "u" will be vertex 'd'. >> Then you do DFS from d, but its out degree is 0. >> So your DFS ends at 'd' itself and you report the solution as b->c->d. >> But the solution is a->b->c->d. What did I miss? >> >> My proposal: >> Topological Sort <http://en.wikipedia.org/wiki/Topological_sorting> the >> graph and keep removing the nodes from vertices which have out degree of 0 >> (given the DAG, there will always be atleast one such vertex). Rest is self >> explanatory :) >> >> >> Veni Vedi Slumber ! >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to algogeeks+unsubscr...@googlegroups.com. >> >> >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to algogeeks+unsubscr...@googlegroups.com. > > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
