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]
Top comments (0)