Depth first search for binary trees

Depth first search (DFS) has got to be one of the most popular computer science concepts especially pertaining to technical interviews. The amount and diversity of questions that can be asked are so broad that there's almost no possible way to cover all of them in a single article. In this article, I'll try my best to go over the basics of depth first search involving binary trees.

What is DFS ???🤔🤔🤔

You may probably know what DFS is but I'll go ahead and explain it anyway.
Depth first search is a mode of traversal (movement) within a tree or graph data structure, where all nodes along a branch or path are checked till the end before any lateral movements are made.
For example, imagine the binary tree below is sent into a dfs function via its root (5). According to the green arrows we see that the function only moves in one direction until it gets to the leaf node (7), before making a lateral movement to (2) (signified by the yellow line).

This form of movement is supported by the stack data structure. How, you ask?🤔 I'll try to explain this with a demonstration. All nodes of a binary tree are pushed into the stack and pushed back out one after the other starting from the end to be examined. Whenever we examine a node, it makes sense to check for right and left children. If a node has a right or left child, we push it back into the stack so we can examine it later. This process is repeated for every node until we get to the leaf node.
Let's go through the process node by node. With the binary tree above as our example let's put the root node into the stack and then remove it to examine it in our table on the right. From the image below we can see that the root node (5) has 2 children (8 & 4). As I said earlier, we'll be pushing both children into the stack so we can examine them.

Now let's remove the next node at the end of the stack for examination. The next node is (4) which only has a left child (11). As mentioned earlier, I'll have to push this node (11) into the stack so I can examine it later.

The next node to be removed from the stack for examination is (11) which has 2 children (7 & 2). I'll have to push these children (7 & 2) into the stack to later examine them.

The next node to be removed from the stack for examination is (7) and for the first time, we have encountered a node that has no children, therefore there are no more nodes to push into the stack. Glancing at the tree we can see that we have examined all the nodes along one branch up until its leaf node (7), before considering a lateral movement.

Our first lateral movement for this tree starts once we remove (2) from the stack for examination.(2) has no children so once again, there are no more nodes to push into the stack.

If you look closely at the stack in the image above, you'll realize that the node (8) which leads to the right branch of the root node has still not been examined. This confirms the concept of first examining the depths of one branch and all its nodes before moving to another.

I'm sure you get the process by now so I'll simply put out the result of the final traversal in the image below. The node column shows all the nodes we traversed through this process. The algorithm breaks once the stack is empty.