Depth Firsrt Search of a Binary Tree or DFS

In case of dfs we will go as deep as possible in the given tree. In BFS we have explored or processed the nodes at the same level then we move further, but that is not the case when we consider DFS.

In DFS we will pick a node then we will pick it's child node(if any) then it's child and so on until we reaches the leaf node.

Let's consider the same tree we constructed in breadth first search post. 

When we talk about traversing a binary tree with depth first search technique then we have tree type of dfs traversal.

1. In Order (left subtree -> current  node -> right subtree)
2. Pre Order (current node-> left subtree -> right subtree)
3. Post Order (left subtree -> right subtree -> current node)

We can achieve DFS by two ways i.e. using iterative (using stack) and using recursion. We will discuss all the traversal methods i.e. inorder, preorder and postorder using iterative and recusrion one by one.

NOTE:  As we know that their are three type of depth search traversal. In order, Pre order and Post order. So the algorithm will be same for all the three types but with a major difference about adding the nodes into the stack( Last In First Out - LIFO). Beacuse incase of In order traversal the the left subtree is processed first, it should the the top element of the stack. To make it a top element we will add it after right subtree, root node. 

Algotuthm For Iterative:

1. We start with the root node and check that, if root is null then we sipmly return.
2. Otherwise we will create a hashset to keep track of the visited nodes.
3. We will be required a stack to push the nodes to process them 1 by 1.
4. Add the current node in the stack to start the traversal.
5. Get the top element and check if it doesn't have left or right subtree then process(print) it.
6. If we have processed all the left subtree then print the current node.
7. Otherwise add the current node in the visited nodes set i.e we visit the current node and mark it as visited.
8. Now add current node's right subtree in the stack.
9. Add the current node in the stack
10. Add the left subtree in the stack 
11. Perform step 5 thorough step 10 until stack is empty i.e. all the nodes have been visited and processed.

Algorithm For Recursion:

1. We start with the root node and check that, if root is null then we sipmly return.
2. We will process the left subtree, current node and right subtree based on the type of traversal we want. 

Adding into the stack order for Iterative method : 

In order ( right subtree, current node, left subtree)

Pre order - (right subtree, left subtree, current node)

Post order - (current node, right subtree, left subtree).

inOrderUsingStack Method definition:

inOrderTraversalUsingRecursion Method definition:

preOrderUsingStack Method definition:

preOrderTraversalUsingRecursion Method definition:

postOrderUsingStack

postOrderTraversalUsingRecursion

**Time Complexity of BFS = O(V+E) where V is vertices and E is edges. Time Complexity of DFS is also O(V+E) where V is vertices and E is edges.