Depth first traversal is a method of traversing trees which explores as far along a given branch as possible before exploring the next branch.

Types

There are 2 general types of depth-first traversal, each of which determines the order in which the root is visited compared to the subtree are visited.

Preorder Traversal

In preorder traversal, the node is processed before its subtrees. This traversal is useful for creating a copy of the tree or generating a prefix notation of an expression tree.

class Node:
    def __init__(self, value, children=None):
        self.value = value
        self.children = children or []


def preorder_traverse(root, visit):
    if root is None:
        return

    visit(root.value)

    for child in root.children:
        preorder_traverse(child, visit)

Postorder Traversal

In postorder traversal, the node is processed after its subtrees. This traversal is useful for tasks such as deleting the tree or generating a postfix notation of an expression tree. It works for general trees as well.

class Node:
    def __init__(self, value, children=None):
        self.value = value
        self.children = children or []


def postorder_traverse(root, visit):
    if root is None:
        return

    for child in root.children:
        postorder_traverse(child, visit)

    visit(root.value)