How to traverse a binary search tree in alphabetical order python?

Question

I need your help or if you can give me advice. I'm really struggling and some help would be perfect, so this is what I got so far;

import BST, TreeNode

class Bibliography:

def __init__(self):
    self.bibtree = BST()

def getReference(self,key):
    """Return the reference for the key, if it exists, otherwise None."""
    theValue = self.bibtree.retrieveKey(key,self.bibtree.root)
    if theValue == None:
        return None
    else:
        return theValue.payload

def addReference(self, key, value):
    """Add the reference represented by key and value.

    Assume the key does not exist in the bibliography.
    """
    self.bibtree.insertNode(key, value)

def removeReference(self, key):
    """Remove the reference with this key.

    Assume the key exists in the bibliography.
    """
    self.bibtree.deleteNode(key)

def outputBibliography(self):
    """Return a string with all references in alphabetical order.

    There must be an empty line after each reference
    """
    return self.traverse(self.bibtree.root)

def traverse(self, aNode):
    """Return a string with the references in the subtree rooted at aNode.

    The references should be ordered alphabetically,
    with an empty line after each reference
    and a space between each key and its value. See the test file.
    """
    if aNode:
      self.traverse(aNode.leftChild)
        return str(aNode.key, aNode.payload, end='\n\n')
      self.traverse(aNode.right)

When I do the test the below function is not working and need help.It returns it as a list in this bracket [ ] and I do not want this. I also want a blank line and this does not happen either. I'm not to sure what I'm doing wrong, if you can give me some advise this will be helpful.

def traverse(self, aNode):
    """Return a string with the references in the subtree rooted at aNode.

    The references should be ordered alphabetically,
    with an empty line after each reference
    and a space between each key and its value. See the test file.
    """
        res = []
        if aNode:
          res = self.traverse(aNode.leftChild)
          res.append(aNode.key + ' ' + aNode.payload + '\n\n')
          res = res + self.traverse(aNode.rightChild)
        return res

The output using this code is:

['Adams, A (1991) Loves football\n\n', 'Marlow, C (1996) Loves cricket\n\n', 'Smith, I (1994) Does not play sports\n\n']

And I want this output:

Adams, A (1991) Loves football

Marlow, C (1996) Loves cricket

Smith, I (1994) Does not play sports

Answer 1

And you are concatenating lists anyways, as in res + self.traverse(aNode.rightChild). Ok, never mind my previous comments about this, you get O^2 there even with lists, because you are copying them all over. Just do this

def traverse(self, aNode):
    res = ""
    if aNode:
        res = self.traverse(aNode.leftChild)
        res += aNode.key + ' ' + aNode.payload + '\n\n'
        res += self.traverse(aNode.rightChild)
    return res

This ends up giving you an empty line after the last reference, so it is more literal implementation of what the assignment says: "... with an empty line after each reference ...". That join() would only insert the newlines between references, and not after the last one.