Lessons · Python · walking a tree
Two ways to visit every node
Depth-first goes all the way down one branch before trying the next, and recursion does it for free. Breadth-first goes level by level, and needs a queue.
Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.
What it is for
Which one you pick changes the answer, not only the speed. Breadth-first reaches a node by a shortest route; depth-first reaches it by whichever route it wandered down first.
How to think about it
Say the requirement out loud. 'In order', 'all of this branch', 'sum down a path': depth-first, write it recursively. 'Level by level', 'nearest first', 'fewest steps': breadth-first, reach for a deque.
Worked example
from collections import dequeBreadth-first needs a queue.
class Node:
def __init__(self, value, left=None, right=None):
self.value, self.left, self.right = value, left, right
root = Node(5, Node(3, Node(1), Node(4)), Node(8, Node(7)))A small search tree.
def inorder(node):Left, self, right.
if node is None: return []
return inorder(node.left) + [node.value] + inorder(node.right)The order of the three pieces IS the walk.
print(inorder(root))[1, 3, 4, 5, 7, 8]
def by_level(node):Breadth-first.
out, q = [], deque([node])Everything still to visit.
while q:
n = q.popleft()The front: the shallowest node still waiting.
if n is None: continue
out.append(n.value)
q.append(n.left); q.append(n.right)Children go to the BACK, so they wait their turn.
return out
print(by_level(root))[5, 3, 8, 1, 4, 7]
Your turn
Make the walk breadth-first rather than depth-first.
q = deque([root])
while q:
node = q.()
q.append(node.left); q.append(node.right)Solve one with the tests running
The trap
Swap popleft() for pop() in that loop and it silently becomes depth-first. Same code, different answer, no error.