Tree traversal algorithm in Python

Posted on Edited on In , Views:

Tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure, exactly once. Such traversals are classified by the order in which the nodes are visited. - Wikipedia

Tree traversal algorithms can be classified in the following two categories:

  • Depth-First Search (DFS): It starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
  • Breadth-First Search (BFS): It starts at the tree’s root (selecting some arbitrary node as the root node in the case of a graph) and searches all nodes at the current depth level before moving on to the nodes at the next depth level.

Depth-First Search (DFS) algorithms have three variants:

  • Preorder Traversal (current-left-right): Visit the current node before visiting any nodes inside left or right subtrees.
  • Inorder Traversal (left-current-right): Visit the current node after visiting all nodes inside left subtree but before visiting any node within the right subtree.
  • Postorder Traversal (left-right-current): Visit the current node after visiting all the nodes of left and right subtrees.

Breadth-First Search (BFS) Algorithm has one variant:

  • Level Order Traversal: Visit nodes level-by-level and left-to-right fashion at the same level.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def pre_order_traverse(node):
    if node == None:
        return

    print(f"{node.val} ", end="")
    pre_order_traverse(node.left)
    pre_order_traverse(node.right)


def in_order_traverse(node):
    if node == None:
        return

    in_order_traverse(node.left)
    print(f"{node.val} ", end="")
    in_order_traverse(node.right)


def post_order_traverse(node):
    if node == None:
        return

    post_order_traverse(node.left)
    post_order_traverse(node.right)
    print(f"{node.val} ", end="")


def level_order_traverse(node):
    if node == None:
        return

    queue = []
    queue.append(node)

    while len(queue) > 0:
        first = queue.pop(0)

        print(f"{first.val} ", end="")

        if first.left != None:
            queue.append(first.left)

        if first.right != None:
            queue.append(first.right)

root = Node(0)
n1 = Node(1)
n2 = Node(2)
root.left = n1
root.right = n2
n3 = Node(3)
n4 = Node(4)
n1.left = n3
n1.right = n4
n5 = Node(5)
n6 = Node(6)
n2.left = n5
n2.right = n6
n7 = Node(7)
n8 = Node(8)
n3.left = n7
n3.right = n8

pre_order_traverse(root)
print()
in_order_traverse(root)
print()
post_order_traverse(root)
print()
level_order_traverse(root)
print()

# Output:
# 0 1 3 7 8 4 2 5 6
# 7 3 8 1 4 0 5 2 6
# 7 8 3 4 1 5 6 2 0
# 0 1 2 3 4 5 6 7 8