1 files changed, 39 insertions, 1 deletions

diff --git a/search.py b/search.py
index 30deb8e..b360091 100644
--- a/search.py
+++ b/search.py
@@ -87,7 +87,45 @@ def depthFirstSearch(problem):
     print "Start's successors:", problem.getSuccessors(problem.getStartState())
     """
     "*** YOUR CODE HERE ***"
-    util.raiseNotDefined()
+
+    def traverse(problem, node, visited):
+
+        # Add nextNode to visited list
+        visited.append(node[0])
+
+        # Recursive base case
+        if problem.isGoalState(node[0]):
+            return [node[1]]
+
+        pq = util.PriorityQueueWithFunction(lambda child: child[2])
+
+        # Get all successors and push them into a priority queue based on cost
+        children = problem.getSuccessors(node[0])
+        for nextNode in children:
+            # Check that nextNode has not been visited
+            if nextNode[0] in visited:
+                continue
+
+            # Push the child if it was not visited
+            pq.push(nextNode)
+
+        while not pq.isEmpty():
+            # Pop lowest cost child from the queue
+            nextNode = pq.pop()
+
+            # Recursive call to nextNode
+            path = traverse(problem, nextNode, visited)
+
+            # Check if recursive call returned values
+            if path != None:
+                # Check to not add the initial node
+                if node[1] != None:
+                    # Add the node the start of the list (reverse it)
+                    path.insert(0, node[1])
+                return path
+
+    return traverse(problem, (problem.getStartState(), None, 0), [])
+
 
 def breadthFirstSearch(problem):
     """Search the shallowest nodes in the search tree first."""