Tree Traversal in Python

Let's say we have the following tree:

tree = {
    5: [3, 7],
    3: [2, 1],
    7: [8],
    2: [],
    1: [],
    8: []
}

There are two ways to traverse this tree
-> Breadth First Search (BFS)
-> Depth First Search (DFS)

BFS can be imagined as horizontal neighbours and DFS can be imagined as vertical neighbours.

Implementation of BFS:

def bfs(tree, node, path=[]):
    queue = [node]
    while queue:
        node = queue.pop(0)
        if node not in queue:
            path.append(node)
            for neighbour in tree[node]:
                queue.append(neighbour)
    return path

Output:

>>> bfs(tree, 5)
    [5, 3, 7, 2, 1, 8]

Implementation of DFS:

def dfs(tree, node, path=[]):
    queue = set()
    if node not in queue:
        queue.add(node)
        path.append(node)
        for neighbour in tree[node]:
            path = dfs(tree, neighbour)
    return path

Output:

>>> dfs(tree, 5)
    [5, 3, 2, 1, 7, 8]

Blog

Tree Traversal in Python

Santhosh Balasa

Join Our Newsletter. No Spam, Only the good stuff.

Related