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. 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. 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. 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. 