0 votes 0 votes preorder traversal of a tree resemble to the DFS traversal of graph? Programming in C data-structures tree-traversal + – S Ram asked Jan 15, 2017 • recategorized Jul 7, 2022 by Lakshman Bhaiya S Ram 1.2k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Rahul Jain25 commented Jan 15, 2017 reply Follow Share You can say that, but will not always true bcoz in preorder after visiting node you have to visit left note if present. Whereas, in DFS after visiting node I can visit left or right. So both are different, but can have implementation where in DFS left node is prefered then it can be same. DFS also works on connected graphs that are not tree, and preorder is for trees. 1 votes 1 votes S Ram commented Jan 15, 2017 reply Follow Share got it bro thanks. :) 0 votes 0 votes Please log in or register to add a comment.
Best answer 2 votes 2 votes It is true if the graph is acyclic.. The logic being in DFS we continue in the path till the leaf level and then backtrack and then go ot other unvisited nodes after backtracking to common ancestor .. In fact DFS can be simulated using any of the postorder , preorder and in order traversal.. For implementation detail of each type , plz check : https://en.wikipedia.org/wiki/Tree_traversal#Implementations Habibkhan answered Jan 15, 2017 • selected Jan 15, 2017 by S Ram Habibkhan comment Share Follow See all 8 Comments See all 8 8 Comments reply Rahul Jain25 commented Jan 15, 2017 reply Follow Share @habib, I have some doubts. How can we implement DFS by inorder??? Also how by post order?? Bcoz as far as I know as soon as you reach a node it isvisited in DFS. And you said true for cyclic graph. Can we apply postorder, inorder, postorder on graphs which have cycles. I thought they were only for trees. 0 votes 0 votes Habibkhan commented Jan 15, 2017 reply Follow Share I said true for acyclic graph i.e. tree..Plz read the reference carefully..U will get it 0 votes 0 votes Rahul Jain25 commented Jan 15, 2017 reply Follow Share Sorry habib, my bad 0 votes 0 votes Shubhanshu commented Jun 5, 2017 reply Follow Share @Arjun sir, @Bikram sir @habib sir, Consider a binary tree. Now in this tree, according to DFS, standing on the root we can either go to LST or RST but in pre order, standing on the root we can only go to left subtree(LST) then how preorder can be resemble as DFS???? 0 votes 0 votes Bikram commented Jun 5, 2017 reply Follow Share yes @Shubhanshu preorder can be resemble as DFS , it is true , as when we perform DFS in a tree, the left-most child searched first (completely), then after backtracking, the second-most-left child... see elow wiki example also say the same , https://en.wikipedia.org/wiki/Depth-first_search#Example it is assumption that in DFs we first visit left child , but this is assumption only, Not a rule https://softwareengineering.stackexchange.com/questions/288702/how-definite-of-an-order-is-there-to-a-depth-first-search-of-a-graph 0 votes 0 votes Shubhanshu commented Jun 5, 2017 reply Follow Share Means DFS can also be said as pre-order traversal but it is not mandatory. ryt? 0 votes 0 votes Bikram commented Jun 5, 2017 reply Follow Share yes, DFS can also be said as pre-order traversal but not mandatory to say that .. it depends upon our assumption only . In that wiki link i gave it is written there A preordering is a list of the vertices in the order that they were first visited by the depth-first search algorithm. This is a compact and natural way of describing the progress of the search ... read vertex ordering part here https://en.wikipedia.org/wiki/Depth-first_search#Example 0 votes 0 votes Shubhanshu commented Jun 5, 2017 reply Follow Share Thanks, @Bikram Sir!! 0 votes 0 votes Please log in or register to add a comment.