13

It seems to me like pre-order traversal and DFS are same as in both the cases we traverse from root till the left branch and back to root and then to the right branch recursively. Could any please correct me if I am wrong?

Thanks in advance!

12

pre order traversal is a traversal, it visits every node in a binary tree

Depth First Search is a search, it goes around an arbitrary graph looking for a certain node (that it works best in a non cyclic graph (a.k.a. tree) is irrelevant)

this alone is a large enough difference to call them difference names

| improve this answer | |
  • 1
    +1, but I'd like to add that pre- and post-order traversals are just special cases of the more general DFS strategy. – Frank Feb 5 '14 at 8:42
  • 1
    Doesn't pre-order traversal simply mean processing nodes before their children? Where does it say that the nodes form a binary tree, or even a tree? – Kilian Foth Feb 5 '14 at 8:54
  • @KilianFoth I would expect the implication of a node having children (as opposed to neighbors) to imply a tree structure since it suggests a hierarchy of nodes. The top of the hierarchy being the root of the tree. But I can imagine pre order traversal and post order traversal making sense on any tree even those that are not binary. – YoungJohn Jul 22 '15 at 19:48
1

Yes, but it should be the opposite way: DFS is similar to PreOrder.
Term PreOrder is more relevant to binary trees and parsers.
It is used to compare with other traversal orders of a binary tree: InOrder, PostOrder and PreOrder.
Topological Sort is similar to Post Order traversal (push the node into stack after visiting all the adjacent nodes).

| improve this answer | |
  • My thoughts are similar to this answer. More specifically, a pre-order is a specific implementation of the parent category of DFS. Pre-order child traversal is rigidly left then right; whereas for generic (parent) DFS, the children's traversal order is not defined and could be any order. – Jerred S. Feb 10 at 14:20
0

To traverse a binary tree in Preorder, following operations are carried-out

  1. Visit the root
  2. Traverse the left subtree
  3. Traverse the right subtree

That is in the below image the pre order traversal would be, 1,2,3,6,4,5,7,8,9,10,11,12

In the same image 1,2,3,4,5,6,7,8,9,10,11,12 would be for DFS

DFS Source : http://datastructuresnotes.blogspot.in/2009/02/binary-tree-traversal-preorder-inorder.html

Pre Order Source : Wiki

DFS

| improve this answer | |
  • 9
    This is not a binary tree. It's a tree, but not binary. – Manoj R Feb 5 '14 at 9:56
  • What happens when "6" has sub nodes? – Marjan Venema Feb 5 '14 at 10:54
  • You are asking for DFS or pre order? – Zedaiq Feb 5 '14 at 11:01
  • @ManojR Got it from the source mentioned above. – Zedaiq Feb 5 '14 at 11:01
  • pre order in this graph gives same answer – Charles Chow Feb 19 '17 at 7:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.