Search code examples
binary-treebreadth-first-searchtree-traversalpreorder

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

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.

Additionally, how does Pre-order traversal compare to Depth First Search traversal (DFS)?

Solution

  • 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:

    counter example 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