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

procedureDFS(G,v)is

labelvas discoveredadd logic when first time node is discoveredfor each neighbour w of v do

ifvertexwis not labeled as discoveredthen

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**