Is Pre-Order traversal on a binary tree same as Depth First Search?

Question

It seems to me like Pre-order traversal and DFS are same as in both the cases we traverse till the leaf node in a depth wise fashion. Could anyone please correct me if I am wrong?

Thanks in advance!

Manas

en.wikipedia.org/wiki/Tree_traversal#Depth-first – Orchidectomy

Answer 1

Pre-order is one type of DFS.

There are three types of depth-first traversal: pre-order, in-order, and post-order.

Check out here for more info.

Uigur

It seems to me that the question is not seeking an advanced asnwer, I think he's looking for Pre-order DFS, which is among common computer major students called "DFS" as a short-term. – Syllabism

I think he has simply observed that when the graph in question is also a tree, and the initial vertex for DFS is the tree's root then DFS and a pre-order traversal are equivalent. In-order traversal has no meaning for k-ary trees where k > 2. – Obligor

Even if the graph were a binary-tree the output of pre-order tree traversal is unlikely to be the same as a walk of the predecessor-subgraph though, unless the vertex adjacency lists consistently enumerate in the same order as they would as node "children" in the tree. That is the graph representation has no notion of "left" and "right" children. – Obligor

There are actually six types of depth-first traversal on a binary tree -- pre-order, post-order, in-order, reverse-pre-order, reverse-post-order, and reverse in-order. This corresponds to the six permutations of three operations (3!) where the operations are "go left", "go right" and "process node". – Ugric

Answer 2

Intuitively, they feel the same due to the way we apply DFS algorithm using recursion (i.e making use of implicit stack data structure) in most of the implementations. In most of the cases (or all) the results are the same as for a Pre-Order Traversal.

The idea of DFS is to pick a branch and go deep into that, explore it completely. Whereas, the fashion of picking the branch and going down is determined by what kind of DFS you are implementing. Just for the sake of completion, in BFS algorithm, we traverse level-wise.

Remember, Pre-Order is just a type of DFS. We also have other methods which are shown below.

Image Source: Base CS

For better understanding, refer this blog or even this one.

Barajas

Answer 3

It won't be. Pre-order has a strict fashion of visiting the Left node and then the Right node. But for DFS it can be either as there is no strict fashion. So, more than one traversal exists based on what you push on the stack.

Capitulation

Answer 4

It probably depends on the definition and implementation of the depth-first algorithm. The DefaultMutableTreeNode class of the Java Swing's JTree component has the following enumeration methods used for tree traversal:

• depthFirstEnumeration()
• postorderEnumeration()
• preorderEnumeration()
• breadthFirstEnumeration()

In Java Swing's implementation the depthFirstEnumeration is the same as the postOrderEnumeration. My tests and the official documentation confirms this.

Others can define what depth-first means differently. For instance, an article on Wikipedia states that pre-order and post-order traversals are specific types of a depth-first traversal. This would mean that the depth-first traversal is not a concrete traversal algorithm.

Sheliasheline

Answer 5

PreOrder Traversal is a type in DFS In DFS there are total 3 types of Traversals:

• InOrder Traversal
• PreOrder Traversal
• PostOrder Traversal

Joachima

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. – Tulatulip