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.

    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