Recursive BFS solution for tree traversal I'm somewhat new to the wonderful world of Python, outside of simple codecademy-like challenges online.

This function was part of a project for school. It's tested and works, but I'm looking for some feedback. Did I over-think it? I don't think recursion was necessary, but I was in that mindset from the previous portion of the assignment which was a similar function for DFS.

Below is my code, the input format (a dictionary) and a visual representation of the tree that I used to test it:

def BFS(tree,level=["A"]):
  bfs_list = []
  if len(level) &gt; 0:
    bfs_list += level
    sub_level = []
    for vertex in level:
      sub_level += tree[vertex]
    bfs_list += BFS(tree,sub_level)
  return bfs_list


#            ___A___
#           /       \
#          C         D
#        / | \     / | \
#       P  R  L   F  Q  S
#         / \       / \
#        O   E     G   H
#                 / \
#                N   M
#
tree = {"A" : ["C", "D"], 
        "C" : ["P","R","L"],
        "R" : ["O","E"],
        "G" : ["N", "M"], 
        "Q" : ["G", "H"], 
        "D" : ["F", "Q", "S"],
        "P" : [], 
        "L" : [], 
        "N" : [], 
        "M" : [], 
        "H" : [], 
        "S" : [], 
        "F" : [], 
        "O" : [], 
        "E" : []}
print(BFS(tree))
You're off to a good start.  In cases like this, most of my comments come down to best-practices for coding standards.  I break down a few areas, starting from nitpicks to almost-bugs:

1. Spacing

In the python world it is worth familiarizing yourself with PEP8, which sets suggested standards for code formatting across the python world.  Yours looks pretty close to most of the standards, but one thing you are missing is your indentation.  2 spaces is pretty small: I would go for 4, which is the PEP8 recommendation.  Also, a space between parameters is recommended.  I.e. tree, level instead of tree,level.  Believe it or not, these things matter: in almost all cases, code is read more than it is written.  As a result, it is important for long-term maintenance to write code that is consistent and easy-to-read.

2. Doc strings

Doc strings are the preferred way of commenting your code.  Comments themselves should be used sparingly (you don't have any, which for a function of this size is fine), but doc strings should be used pretty much everywhere.  These are a formatted block of text, inside a comment, that comes right before your function definition (also classes and modules).  It describes the parameters, what the function does, and what it returns.  See here:

https://stackoverflow.com/a/24385103/1921979

3. Guard conditions

Instead of putting all of your code inside an indented block, this is one of many cases where a guard clause will make your code more readable.  At the top, put conditions on cases where you don't need to do any processing, and exit early.  I.e.:

if not level:
    return []
// everything else here


4. Recursion

Recursion here is perfectly fine.  You didn't overthink it or overdo it.  It actually fits perfectly in this case, and recursion is usually a harder concept to grasp, so anything that helps you practice it (without making the code a tangled mess) is a good choice.

5. Default parameter values

Your default value for the level parameter only works for your given example.  As a result, it is best to kill it.  Just make it a required positional parameter.

6. Error detection

Your code assumes that it is passed in a valid tree.  This is not a crazy assumption, but it will likely be a wrong assumption at some point in time.  In your current case, if someone passes in a broken tree, it will generally lead to an exception being raised.  This can be a good thing or bad thing depending on your viewpoint.  There are three ways I normally consider handling such an event (in order of preference):


Detect and raise an exception
Ignore and let python raise an exception
Silently ignore it


Here is a simple example of a tree that will fail:

tree = {"A" : ["C", "D"]}


Your current code opts for Option #2 above.  With the above example, python will raise a KeyError with a rather cryptic message: KeyError: 'C'.  This is not necessarily a bad thing.  Garbage In=Garbage Out.  However, the problem is that it might not be obvious what caused the error.  As a result I like to detect and raise my own exceptions to make it easier on whoever is using your method (Option #1):

for vertex in level:
    if tree not in vertex:
        raise ValueError('Broken tree: branch %s is referenced but not found in the tree' % (vertex))
    sub_level += tree[vertex]


This gives the user better information on where to start looking for the problem: most importantly, not in your function.  The third option would be to silently ignore such errors.  That would look something like this:

for vertex in level:
    if vertex not in tree:
        continue
    sub_level += tree[vertex]


This can be appealing because it makes your code play nicer if a broken tree comes its way.  The problem is that this can often end up hiding bugs, which just cause problems farther down the stack.  The farther your code gets before it crashes, the harder the problem tends to be to resolve.  So my default is to quit loudly if something is off.  That is what logging is for.