Tree Traversals: Depth First Search (DFS)

Tree Traversals: Depth First Search (DFS)

The term traversal means to visit each node in a tree exactly once. In linear lists the order of traversal is vividly first to last. However, in trees there exists no such natural linear order.In this article, depth first search is studied.

Tree Traversal : DFS

More Information About DFS:

DFS can be defined as an algorithm, based on backtracking, dedicated to traversing a tree structure by first visiting the root first and then the left sub-tree and the right sub-tree.

  • It is of three types:
    • In-order traversal.

    • Pre-order traversal.

    • Post-order traversal.

Preorder Traversal:

For traversal of a non-empty binary tree or binary search tree in Pre-order, following sequence of operations is performed.

  1. Visit the root node.
  2. Traverse the left sub tree in pre-order.
  3. Traverse the right sub tree in post-order.
Example Of Preorder Traversal - BFS

Inorder Traversal:

For traversal of a non-empty binary tree or binary search tree in In-order, following sequence of operations is performed.

  1. Traverse the left sub tree in in-order.
  2. Visit the root node.
  3. Traverse the right sub tree in in-order.
Example Of Inorder Traversal - DFS

Postorder Traversal:

For traversal of a non-empty binary tree or binary search tree in Post-order, following sequence of operations is performed.

  1. Traverse the left sub tree in post-order.
  2. Traverse the right sub tree in post-order.
  3. Visit the root node.
Example Of Postorder Traversal : DFS