A Node-based class of connected nodes is a standard approach. These can be hard to visualize.
Motivated from an essay on Python Patterns - Implementing Graphs, consider a simple dictionary:
Given
A binary tree
a
/ \
b c
/ \ \
d e f
Code
Make a dictionary of unique nodes:
tree = {
"a": ["b", "c"],
"b": ["d", "e"],
"c": [None, "f"],
"d": [None, None],
"e": [None, None],
"f": [None, None],
}
Details
find_all_paths()). Tree-based functions often include the following common operations:
Try implementing all of these operations. Here we demonstrate one of these functions - a BFS traversal:
Example
import collections as ct
def traverse(tree):
"""Yield nodes from a tree via BFS."""
q = ct.deque() # 1
root = next(iter(tree)) # 2
q.append(root)
while q:
node = q.popleft()
children = filter(None, tree.get(node))
for n in children: # 3
q.append(n)
yield node
list(traverse(tree))
# ['a', 'b', 'c', 'd', 'e', 'f']
This is a breadth-first search (level-order) algorithm applied to a dict of nodes and children.
deque, but a queue or a list works (the latter is inefficient).See also this in-depth tutorial on trees.
Insight
Something great about traversals in general, we can easily alter the latter iterative approach to depth-first search (DFS) by simply replacing the queue with a stack (a.k.a LIFO Queue). This simply means we dequeue from the same side that we enqueue. DFS allows us to search each branch.
How? Since we are using a deque, we can emulate a stack by changing node = q.popleft() to node = q.pop() (right). The result is a right-favored, pre-ordered DFS: ['a', 'c', 'f', 'b', 'e', 'd'].