# Breadth-first search on a tree in Python

The following code performs breadth first search on a mockup tree

# some tree
#             A            - LAYER 0
#         B       C        - LAYER 1
#      D     E             - LAYER 2
#   F                      - LAYER 3

def get_something(x):
if x == 'a':
return ['b', 'c']
if x == 'b':
return ['d', 'e']
if x == 'c':
return []
if x == 'd':
return ['f']
if x == 'e':
return []
if x == 'f':
return []


and it is traversed by the following not so beautiful code

# I mean it works, but looking at it makes me feel sick

def recursive_get(x, loop_limit, count_limit):

# stop condition 1: loop limit exceeded and nonzero
# stop condition 2: count limit exceeded and nonzero
# stop condition 3: we have reached the bottom

current = 0
seen_list = []
todo_list = [x]

while ((current < loop_limit or loop_limit == 0) and
(len(seen_list) < count_limit or count_limit == 0) and
todo_list):

result = get_something(todo_list.pop(0))
seen_list.extend(result)
todo_list.extend(result)
current += 1

return seen_list


Is there any syntactic sugar to get the second part to look more sexy? (less lines, syntactically nicer looking)?

get_something is not a good name for the function. Obviously, it specifies your tree by returning the child nodes of an argument node; rename to, say, get_neighbors. Also, your implementation overkills breadth-first search a bit. See what I mean:

def get_neighbors(x):
if x == 'a':
return ['b', 'c']
if x == 'b':
return ['d', 'e']
if x == 'c':
return []
if x == 'd':
return ['f']
if x == 'e':
return []
if x == 'f':
return []

return [] # Other nodes have no neighbors.

def bfs(start):
queue = [start]
visited = set(start)

while queue:
node = queue.pop(0)

for neighbor in get_neighbors(node):
if neighbor not in visited:
queue.append(neighbor)

Also, note that seen_list should be rather a Python set as operating on it is more efficient than on lists.
• I would probably call it getSiblings or getSibling because of the fact there is only 1 neighbor/sibling. But I prefer sibling, especially if you are going to use the terms parent and child for nodes uphill or downhill. – Malachi Mar 22 '16 at 12:14
• Not all operations on sets are more efficient. Adding an element should be faster with a normal list. For checks with in your statement is correct though. – AlexV Mar 23 '16 at 0:00