Trees are an almost universaldata 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 starts with the root node, then visits 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 inDFS (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.
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.
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 awhile loopto 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. alinked 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 islogarithmicwith 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.
|An intuitive way of visiting a tree, as visits the root node first||Not suitable when we need to visit child nodes first|
|Easy to reproduce exact tree structure||Can have higher space complexity, particularly when done recursively|
|Flexible in implementation||Order of visitation isn t flexible|
As you can see, there are many benefits to preorder traversal, but it can bememory-expensiveand 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.
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.