Implement a method to find a node in a graph using Depth First Search.

Example: apple / \ banana mango / \ / peach strawberry \ / cherry Find cherry ==> true

Need a **hand?** Try out these hints, one at a time.

The key here is to search a

`node`

exhaustively before visiting another `adjacent node`

i.e. let's say if `node n`

, which is adjacent to `root r`

is visited, then before visiting other `adjacent nodes`

of `root r`

, we need to visit `n's adjacent`

nodes. The best iterative approach would be to use a `Stack`

.
1. If `root`

or the `input`

data is `null`

then return false, else ...

2. Declare and initialize a `Stack`

to store objects of type `Node`

.

3. Add the root node to the `Stack`

, and set its `visited`

property to `true`

.

4. Start the `first loop`

to run till the `Stack`

becomes `empty`

.

5. Within the `loop`

, `pop`

an object from the Stack. Check its data and if it is equal to the input data, return `true`

.

6. Else, traverse through all its adjacent nodes using a second `inner loop`

, mark their visited property to true and push them to the `Stack`

.

7. Outside the `first loop`

,return `false`

, which indicates that the data was not found in the `graph`

.

public boolean depthFirstSearch(Node rootNode, String data){ }

**C**

**Java**

**Python**