Depth-First Search

Intro

There are two ways to traverse the tree data structure: Breadth-first search (BFS) and Depth-First Search (DFS).

We've already covered the BFS and Order Lever traversal of a Binary Tree. Here, we will explore the Depth-First Search algorithm and the ways we can traverse the tree using it.

More on Depth-First Search

First, let's see what is a Tree traversal?

Tree traversal is also sometimes referred to as tree search.

When we search through a tree, we’re usually doing it to serve the purpose of either checking all the nodes in the tree structure or updating all the nodes in the structure.
Whichever of these two is the case, there’s one important thing to note here: we’re not going to search through the nodes of a tree more than once. If we’re trying to check or update every single node in a tree, we wouldn’t want to repeat ourselves by visiting a node more than once.

So, when we traverse through a tree, what we’re really trying to do is walk through the tree without ever repeating ourselves.

But it’s not just visiting each node only once that counts — order matters, too.
It turns out that, when it comes to trees, there are really only two main techniques that we can lean on when it comes to traversing and visiting each node in the tree only once. Ultimately, we have two choices: we can go wide (BFS), or we can go deep (DFS).

We've already seen that in the BFS, we traverse the tree level by level.

In depth-first search, once we start down a path, we don’t stop until we get to the end. In other words, we traverse through one branch of a tree until we get to a leaf, and then we work our way back to the trunk of the tree.

Here is a good illustration of BFS and DFS way of traversing:

There are a few different ways that we could search through the children, grandchildren, and great-grandchildren nodes of a tree. And it all comes down to the order in which we visit the nodes.

Therefore, there are three different DFS strategies we can use to traverse the tree, and it all revolve around the order in which we do traversal.

DFS strategies for tree traversal:

1. Preorder: Read the data of the node, then visit the left subtree/nodes, followed by the right subtree/nodes.
2. Inorder: Visit the left subtree/nodes, then read the data of the node, and finally visit the right subtree/nodes.
3. Postorder: Visit the left subtree/nodes, then visit the right subtree/nodes, and finally read the data of the node.

In the upcoming posts, we will cover all the above strategies separately.

Time Complexity of a DFS is O(n) since we are visiting each node of a tree.

Space Complexity: The length of the longest path = m. For each node, we have to store its siblings so that when you have visited all the children, and you come back to a parent node, you can know which sibling to explore next.
For m nodes down the path, we will have to store b nodes extra for each of the m nodes. So the space complexity is O(bm).