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 Show 5 previous comments 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.