title: Traversing a binary tree using linked list
body: <p>I am trying to do a preorder traversal of binary tree using a linked list.</p>
  
  <pre><code>class BTNode:
  """A node in a binary tree."""
  
      def __init__(self: 'BTNode', item: object, 
               left: 'BTNode' =None, right: 'BTNode' =None) -&gt; None:
  
          self.item, self.left, self.right = item, left, right
  
  
  class LLNode:
      """A node in a linked list."""
  
      def __init__(self: 'LLNode', item: object, link: 'LLNode' =None) -&gt; None:
  
          self.item, self.link = item, link
  
      def __str__(self: 'LLNode') -&gt; str:
          """Return an informative string showing self
  
          &gt;&gt;&gt; b = LLNode(1, LLNode(2, LLNode(3)))
          &gt;&gt;&gt; str(b)
          '1 -&gt; 2 -&gt; 3'
          """
          return str(self.item) + (' -&gt; ' + str(self.link) if self.link else '')
  
  
  
  
  def preorder(root: BTNode) -&gt; LLNode:
      """Return the first node in a linked list that contains every value from the
      binary tree rooted at root, listed according to an preorder traversal.
  
      &gt;&gt;&gt; b = BTNode(1, BTNode(2), BTNode(3))
      &gt;&gt;&gt; repr(preorder(b))
     'LLNode(1, LLNode(2, LLNode(3)))'
     &gt;&gt;&gt; b2 = BTNode(4, BTNode(5))
     &gt;&gt;&gt; b3 = BTNode(7, b, b2)
     &gt;&gt;&gt; str(preorder(b3))
     '7 -&gt; 1 -&gt; 2 -&gt; 3 -&gt; 4 -&gt; 5'
      """
  
      return _preorder(root)[0]
  
  def _preorder(root: BTNode) -&gt; (LLNode, LLNode):
      """Return the first and last nodes in a linked list that contains every
      value from the binary tree rooted at root, listed according to an preorder
      traversal.
      """
  
      if not root:
          return None, None
  
      left_head, left_tail = _preorder(root.left)
  
      right_head, right_tail = _preorder(root.right)
  
      # change from right_tail = left_tail to right_tail = left_head
      if not right_tail:
          right_tail = left_head
  
      if not left_head:
          left_head = right_head
  
      if left_tail:
          left_tail.link = right_head
  
      root_node = LLNode(root.item, left_head)
  
      return root_node, right_tail
  </code></pre>
  
  <p>I am always getting '7 -> 1 -> 2' instead of '7 -> 1 -> 2 -> 3 -> 4 -> 5' as my output in preorder function. I am not quite sure why. Could someone please tell me how I can edit my current code to fix this problem? </p>