Home

 › 

Articles

 › 

Understanding Preorder Traversal, With Examples

Preorder Traversal

Understanding Preorder Traversal, With Examples

Key Points

  • Preorder traversal is a method of visiting nodes in a tree, starting from the root node and exploring left and right branches. Preorder traversal can be implemented recursively or iteratively.
  • It has many applications in computer science, including creating and performing operations on trees and DFS algorithms.
  • Pros of preorder traversal include intuitive tree visiting, implementation flexibility, and ease of reproducing exact tree structure.
  • Cons include higher space complexity and rigidity in order of visitation.
  • Common applications of preorder traversal include constructing and deconstructing trees, converting expressions, evaluating expressions, copying trees, and generating prefixes.

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.

Preorder traversal is implemented with a recursive method.

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.

Preorder traversal is done iteratively, using a stack structure to store the nodes.

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.

ProsCons
An intuitive way of visiting a tree, as visits the root node firstNot suitable when we need to visit child nodes first
Easy to reproduce exact tree structureCan have higher space complexity, particularly when done recursively
Flexible in implementationOrder of visitation isn’t flexible

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.

Frequently Asked Questions

What is preorder traversal?

Preorder traversal is a method of visiting the nodes in a tree, which begins at the root node, then explores the left and right branches in turn.

What's the difference between preorder traversal and inorder traversal?

Inorder traversal visits the left branch first, then the root, ending with the right branch. This is often used for sorting a tree, as well as analyzing expressions.

How do we implement preorder traversal?

Preorder traversal is implemented either recursively or iteratively, which implicitly and explicitly call a stack structure respectively.

What is the time complexity of preorder traversal?

The time complexity is equal to O(n), where n is the number of nodes. For an unbalanced tree, this can change to O(n2).

What is the space complexity of preorder traversal?

This depends on how balanced the tree is, but is usually equal to O(h), where h is the height of the tree. For a well-balanced tree, this can be O(log n), but for an unbalanced tree, the complexity can be as high as O(n), such as in a linear-like structure.

What is preorder traversal used for?

Common applications include constructing and deconstructing trees, converting expressions, evaluating expressions, copying trees and generating prefixes.

To top