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) is2   label v as discovered3   for each neighbour w of v do4     if vertex w is not labeled as discovered then5           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 discoveredadd logic when first time node is discoveredfor 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 childrenreturn coinsend`

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