Depth First Search (DFS) Theory

In Depth First Search (DFS), a tree is traversed vertically from top to bottom, or bottom to top. As you might guess from its namesake, we will traverse as deeply as possible, before moving on to a neighbor node. There are three main ways to apply Depth First Search to a tree.

They are as follows:

• Preorder Traversal - We start from the root node and search the tree vertically (top to bottom), traversing from left to right. The order of visits is ROOT-LEFT-RIGHT.

• In-order Traversal - Start from the leftmost node and move to the right nodes traversing from top to bottom. The order of visits is LEFT-ROOT-RIGHT.

• Post-order Traversal - Start from the leftmost node and move to the right nodes, traversing from bottom to top. The order of visits is LEFT-RIGHT-ROOT.

Let's focus on Preorder Traversal for now, which is the most common type of depth first search.

If you traverse the example tree in this article using Preorder Traversal, the tree nodes will be traversed in the following order:

1A-B-D-E-H-I-C-F-G-J