Understanding Preorder Traversal, With Examples

Trees are an almost universal data structure, and as such, are found in most programming languages. The exact implementation may differ, but many of the fundamental operations remain the same. When you’re working with trees, you’ll often need to visit the elements within the tree. This process is known as traversal and is often carried out in a particular order. One example of this is preorder traversal, which is the focus of this article. Come with us as we explain how preorder traversal works and how to implement it, along with its best practices and practical applications.

What is Preorder Traversal, and Why is it Important?

When we have a binary tree, we have a root node with two branches. These branches have their own nodes, which in turn branch out to further nodes until the structure is complete. There are many ways to visit these nodes. The three main methods are:

• Inorder traversal – this is where we recursively visit the left subtree, visit the root node and then explore the right subtree. Inorder traversal works in ascending order, so is often used to create a sorted list.
• Postorder traversal – this process visits the left and right subtrees first, then ends up at the node. This is often used to delete trees.
• Preorder traversal – the topic of this article, preorder traversal involves starting with the root node, then visiting the left and right subtrees in turn.

Preorder traversal is important because it has many applications in computer science. It’s not only used to create trees in the first place but for performing operations on trees. This is because it visits the nodes in a specific order so that the properties of the tree are preserved. As such, preorder traversal is often used in DFS (Depth-First-Search) algorithms, where we want to explore the structure deeply along each branch.

Implementation of Preorder Traversal

There are two main ways to use preorder traversal – either recursively or by using a stack structure. Let’s explore these in turn.

Recursive method

The general syntax for recursive preorder traversal can be described as follows:

preorderTraversal(node):
    if node is null:
        return

    process(node)

    preorderTraversal(node.left)

    preorderTraversal(node.right)

First, we check if the node is null. If it is, there are no more nodes to look at. Otherwise, we perform the operations we want on the node, then recursively call the function on the left and right subtrees in that order. Let’s look at an example in Python:

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def preorderTraversal(node):
    if node is None:
        return

    print(node.value)

    preorderTraversal(node.left)

    preorderTraversal(node.right)

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

preorderTraversal(root)

We start by declaring the “TreeNode” class, which contains the “__init__” constructor method, which takes “self” and “value” as arguments. A class instance is initialized with the “value” parameter, and “self” refers to the current instance.

We then assign the “value” parameter to the attribute of the current instance, and initialize both the “left” and “right” attributes to “None”.

After that, a function called “preorderTraversal(node)” is defined, which is used to perform the traversal. The current node is represented by “node”. If the node is equal to None, then no further operations are required. The value of the current node is then printed.

The main function is then called on both the left and right nodes recursively. Finally, we create a binary tree, with the root node being 1, the first left and right child nodes being 2 and 3, the second left and right child nodes being 4 and 5, and so on. The main function is called, starting at the root of the tree, and the results are printed. These can be seen in the image below.

Iterative method

The other way to conduct a preorder traversal is iteratively, using a stack structure to store the nodes before we visit them. Consider the following code block:

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def iterativePreorderTraversal(root):
    if root is None:
        return

    stack = []
    stack.append(root)

    while stack:
        node = stack.pop()

        print(node.value)

        if node.right:
            stack.append(node.right)
            
        if node.left:
            stack.append(node.left)

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

iterativePreorderTraversal(root)

We create the same class as before, with the same constructor method, initializing the left and right nodes to “None”. We then define the main iterative method, “iterativePreorderTraversal(root)”, which takes the root node as input.

After, we create a stack, and add the root node to it. We then use a while loop to perform the main operation of the program. This continues as long as there are nodes in the stack. When a node is removed, the value is printed to the console. The right nodes are added first because stacks operate on the Last-In-First-Out (LIFO) principle. Therefore, if we want to process the left nodes first, they must be added last.

A similar binary tree is created, the main function called, and the nodes printed. The output is in the image below.

The Complexity of Preorder Traversal

Fortunately, the time complexity for preorder traversal in binary trees is often equal to O(n), where n is the number of nodes. In other words, the complexity is dependent on the number of nodes in the tree. This is because we must visit each node once, whatever method we use. In the best case, where we only have one node, this will take constant time, or O(1). However, this situation is very unlikely, so in most cases the complexity is O(n). We can potentially have a worst-case complexity of O(n2) when the tree is basically linear, i.e. a linked list. Again, this would be a rare case of using preorder traversal.

The space complexity is usually equal to O(h), where h is the tree height. However, this can change to O(log n) in the case of a balanced tree, because the height is logarithmic with respect to the number of nodes. This is where the height is a lot smaller than the total node number. For the worst-case unbalanced tree, the complexity approaches O(n), as it’s dependent on the number of nodes.

Pros, Cons, and Applications of Preorder Traversal

As with any method, there are pros and cons. These are described in the table below.

As you can see, there are many benefits to preorder traversal, but it can be memory-expensive and is quite rigid in its execution. Because it visits nodes in a natural way, we can use it to reconstruct the original tree structure from a set of values relatively easily. Likewise, we can use it to deconstruct a tree, that will be reconstructed later. Preorder traversal is also helpful for converting expressions, such as from infix to prefix or postfix. Lastly, DFS algorithms make use of preorder traversal, where every node is visited in order to solve a problem.

Wrapping Up

When we want to traverse a tree in a specific and intuitive order, preorder traversal is a very useful technique to be aware of. While it may not be flexible by design, it can be done either recursive or iterative, depending on your needs. Its main use is to reconstruct or deconstruct a tree, as well as in DFS algorithms. Since it represents the natural way we process tree structures, knowing how preorder traversal works will inevitably help you in your programming journey.

The image featured at the top of this post is ©Edler von Rabenstein/Shutterstock.com.