DFS (Depth First Search) on tree or graph

Consider this tree  (which is a graph without a cycle) :

Now DFS means traversing to the depth...and then going up, so here DFS traversal will result in 5 2 -4 3 21 19 25. We can use non recursive as well recursive approach to solve this problem.

A depth first search (DFS) through a tree starts at the root and goes straight down a single branch until a leaf is reached. Then, it continues at the nearest ancestor that hasn't been searched through yet. DFS uses much less memory than BFS since there is no need to store all the nodes on one level. DFS also does not search the lowest level last, so if your target is likely a leaf near the bottom of the tree, DFS will typically run faster than BFS.

Recursive Solution
Depth First Search (DFS) is a generalization of the preorder traversal. Starting at some arbitrarily chosen vertex v, we mark v so that we know we've visited it, process v, and then recursively traverse all unmarked vertices adjacent to v (v will be a different vertex with every new method call). When we visit a vertex in which all of its neighbors have been visited, we return to its calling vertex, and visit one of its unvisited neighbors, repeating the recursion in the same manner. We continue until we have visited all of the starting vertex's neighbors, which means that we're done. The recursion (stack) guides us through the graph.

public void depthFirstSearch(Vertex v)
{
        v.visited = true;

        // print the node

        for(each vertex w adjacent to v)
        {
           if(!w.visited)
           {
              depthFirstSearch(w);
           }
        }
}

DFS on tree:

void treeDFS(node *root)
{
    printf("[%d] ", root->value);
    root->visited = 1;

    if (root->left)
    {
      if(root->left->visited==0)
      {
        treeDFS(root->left);
      }
    }

    if (root->right)
    {
      if(root->right->visited==0)
      {
        treeDFS(root->right);
      }
    }
}

Non Recursive solution
DFS is a first in last out search. It is a recursive process. Recursion uses a stack implicitly. So, a non-recursive version of DFS can be done using a stack. Since we want to hold off visiting a particular node until all of its children are visited, we have to push the node again on the stack. We need to differentiate when we revisit the node ("back-tracking" in recursion) so that we do not push its children again on the stack. For that we use a Hashmap data structure which serves as a flag to denote if a node is already visited and its children are added to the stack.

void dfs_nonrecursive(Node root) : 

    Stack stack = new Stack()
    stack.push(root)
   
    Hashmap visited = new Hashmap()
    while true :
        curr = stack.pop()
        if curr == null:
            break
       
        //if curr has children and curr not in visited
        if (curr.left != null || curr.right != null) && visited.get(curr) == null :
            stack.push(curr)
            stack.push(right)
            stack.push(left)
           
            visited.put(curr)
            continue
       
        curr.printValue()

Time: We visit the non-leaf nodes (n/2) twice and the leaf nodes (n/2) once. So, 2*(n/2) + n/2 = O(3n/2) i.e. still O(n) time.

Space: Hashmap visited saves references to the non-leaf nodes only. For tree of n nodes, visited would saves 2^logn-1 = n/2 still O(n) space. The stack would save only O(logn) nodes.