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.

Graph Representations:

There are three representation formats for Graph. Let’s have a look at it.

1.Adjacency list:

Vertices are stored as records or objects, and every vertex stores a list of adjacent vertices.

2.Adjacency matrix:

Using 1 and 0 to indicate if two nodes are corrected. The row represents source vertices and the column represents the destination vertices. Only the cost for one edge can be stored between each pair of vertices.

3. Incidence matrix(Boolean matrix or Edge list):

A two-dimensional boolean matrix, in which the rows represent the vertices and columns represent the edges.

Tree Basic

Tree Categories:

Tree is a special edition of Graph. As the tree is just a graph without a cycle.

There are two main categories of trees:

1. Unordered tree
2. Ordered tree

There are so many subcategories in the ordered tree we will not cover all of them in this article.

Graph Search and Tree Traversal

There are two basic categories of Graph Search:

• Breadth-First Search (BFS)
• Depth-First Search (DFS)

The main differences between BFS and DFS are:

• Data Structure: DFS make use of a stack to manage the data but BFS make use of a queue to manage the data
• Purpose: DFS is good at looking for a particular item, while BFS is good at broadly search.

BFS Code:

DFS Code:

Tree Traversal (Inorder, Preorder, and Postorder)

After understanding DFS and how to implement DFS then it is easy to understand Tree Traversal.

Believe it or not, Without modifying anything your DFS code is Inorder tree traversal.

Preorder + Inorder + Postorder (Non-Recursive):

Preorder + Inorder + Postorder (Recursive):

Commons And Differences

Graph Search:

DFS: recursive and use stack data structure. suitable for search certain target

BFS: make use of the queue to manage the state. suitable for a broad search(e.g. find the shortest path)

Tree Traversal:

Preorder: Root -> Left -> Right

Inorder: Left -> Root -> Right

Postorder: Left -> Right -> Root

As I mentioned in the first mindmap, preorder, inorder, and postorder can be treated as variations of DFS. The only differences are the order.

Summary:

This article is to compare with Graph Search(DFS, BFS) and Tree Traversal(preorder, inorder, and postorder). Let me know if you find anything wrong with this article I will fix it.

If you find this article useful, please give this article a thumbs-up.

Reference:

[1]https://zhuanlan.zhihu.com/p/98406357

[2]https://www.geeksforgeeks.org/difference-between-graph-and-tree/#:~:text=Graph%20vs%20Tree&text=Graph%20is%20a%20non%2Dlinear,a%20non%2Dlinear%20data%20structure.&text=It%20is%20a%20collection%20of,collection%20of%20nodes%20and%20edges.