# Is Pre-Order traversal same as Depth First Search?

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?

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

• +1, but I'd like to add that pre- and post-order traversals are just special cases of the more general DFS strategy. Feb 5, 2014 at 8:42
• 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? Feb 5, 2014 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. Jul 22, 2015 at 19:48
• Per these being for binary trees only, that is patently untrue. Only inorder traversal applies specifically to binary trees; pre- and post-order are general graph traversal terms. Mar 5, 2021 at 11:05

Pre-order traversal and DFS can produce the same result. However, their capabilities are different, in that traversals are only for trees, but DFS is for any graph. All trees are graphs, but not all graphs are trees.

Tree traversal means you visit every node in the tree. Depth-First-Search means you are searching for one specific node in a graph. There are 4 acknowledged tree traversals:

1. Pre-order
2. In-order
3. Post-order
4. Level-order (BFS)

Of these traversals, DFS will produce an identical result to pre-order, when you use DFS as a traversal. The way to do this would be to specify an element that does not exist in the graph, and process all the elements DFS encounters along the way - this would essentially become a traversal.

Here's an excerpt from a notable algorithms textbook

Depth-first search (DFS) is a method for exploring a tree or graph. In a DFS, you go as deep as possible down one path before backing up and trying a different one. DFS algorithm works in a manner similar to preorder traversal of the trees. Like preorder traversal, internally this algorithm also uses stack. - Data Structures and Algorithms Made Easy Java 5ed by Karumanchi N.

• `> Depth-First-Search means you are searching for one specific node in a graph.` I'm not so sure about that. DFS is graph traversal, the idea is to for given graph `G` and starting vertice `s` return collection of all vertices reachable from vertice `s`. Jan 25, 2023 at 13:13

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).

• 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. Feb 10, 2020 at 14:20

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

Pre Order Source : Wiki

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