title: Finding the (guaranteed unique) path between two nodes in a tree
body: <p>I have a (likely) simple graph traversal question. I'm a graph newbie using networkx as my graph data structures. My graphs <em>always</em> look like this:</p>
  
  <pre><code>             0
        1              8
     2     3       9      10
   4  5   6 7    11 12  13  14
  </code></pre>
  
  <p>I need to return the path from the root node to a given node (eg., <code>path(0, 11)</code> should return <code>[0, 8, 9, 11]</code>).</p>
  
  <p>I have a solution that works by passing along a list which grows and shrinks to keep track of what the path looks like as you traverse the tree, ultimately getting returned when the target node is found:</p>
  
  <pre><code>def VisitNode(self, node, target, path):
      path.append(node)
      # Base case. If we found the target, then notify the stack that we're done.
      if node == target:
          return True
      else:
          # If we're at a leaf and it isn't the target, then pop the leaf off
          # our path (backtrack) and notify the stack that we're still looking
          if len(self.neighbors(node)) == 0:
              path.pop()
              return False
          else:
              # Sniff down the next available neighboring node
              for i in self.neighbors_iter(node):
                  # If this next node is the target, then return the path 
                  # we've constructed so far
                  if self.VisitNode(i, target, path):
                      return path
              # If we've gotten this far without finding the target, 
              # then this whole branch is a dud. Backtrack
              path.pop()
  </code></pre>
  
  <p>I feel in my bones that there is no need for passing around this "path" list... I should be able to keep track of that information using the call stack, but I can't figure out how... Could someone enlighten me on how you would solve this problem recursively using the stack to keep track of the path?</p>