Depth-first search is a way to explore nodes in a tree or graph.

suppose you are somewhere and want to visit your friend’s home. you are new and don’t have anyone to guide you.

what you can do, start from the source and start walking until you find a blocker then you go back until one new path found.

you stop finally found your destination.

1 procedure DFS(v) is
2   label v as discovered
3   for each neighbour w of v do
4     if vertex w is not labeled as discovered then
5           recursively call DFS(w)

code explanation -

suppose v = 5 neighbours = [ 6, 7, 8 ] , discovered started = empty

line -1 , 5 is discovered

loop

iteration -1 , DFS(6)

iteration-2 start when iteration-1 as exploration from 6 is done , DFS(7)

iteration-3 start when iteration-2 as exploration from 7 is done , DFS(8)

finally neighbours are discovered. and finally exploration of 5 is done.

how to solve the problem using the DFS approach

procedure DFS(G, v) is
    label v as discovered
add logic when first time node is discovered
for each neighbour w of v do
        if vertex w is not labeled as discovered then
            recursively call DFS(G, w)
add logic when node is completed discovered or all its children is finished

example — calculate total coins after visiting all nodes in the binary tree

procedure Ask(v) is
    coins = v ;
// now ask from both its children 
 if left child exist 
   coins+ = Ask(leftChild)
 if right child exist
  coins+ = Ask(RightChild)
// once received answer from both of children
return coins
end

the output from parent requires to finish all its children then, DFS can be a possibility there.

for this, you need to write a reoccurrence relation.

simple reoccurrence may be

the output from parent = left subtree + right subtree