Breadth First Search Traversal VS Pre-order Traversal VS Depth First Search Traversal

Question

For a binary tree, is Breadth First Search traversal (BFS) the same as Pre-order traversal? I am a little bit confused by these two different types of traversals. Can anyone please explain this to me? Additionally, how does Pre-order traversal compare to Depth First Search traversal (DFS)?

Thank you so much!

Answer 1

No, pre-order traversal is actually a form of Depth-First-Search (DFS) traversal. There are three different forms of DFS, namely:

1. Pre-Order
2. In-Order
3. Post-Order

To prove that Breadth-First-Search (BFS) traversal isn't the same as pre-order traversal I will show a counter example below:

To be clear a binary tree isn't the same as a binary search tree, namely a binary tree can be defined as:

Binary Tree - A tree whose elements have at most 2 children is called a binary tree. Note there is no mentioning of the ordering of the children.

Ok now to the counter-example, take the following simple binary tree:

For a pre-order traversal the nodes are visited in the following order: Pre-Order: [1,2,4,3]

now for Breadth-First-Search traversal the nodes are visited in the following order:

BFS: [1,2,3,4]

Note: pre-order traversal is different from the BFS traversal.

For more information on the different tree traversals check out this link

Hopefully, that helps!

Answer 2

DFS types are pre-order , in-order and post-order;

DFS is like - first go for my descendants (grand-grand-..child) then I will see my siblings descendants. BFS is like - first go for my siblings then their child then their child and so on.

pre-order DFS technique is generally used in graph traversal .

in-order traversal only in binary tree.(tree is special kind of graph)

BFS is a level order traversal in the case of tree.

These four are different techniques of traversal and results are also different. Sometimes their result might be same so don't get confused, check for different tree and you will find out difference.