Preorder Traversal

In this article, we will discuss the preorder traversal in data structure. Linear data structures such as stack, array, queue, etc., only have one way to traverse the data. But in a hierarchical data structure such as tree, there are multiple ways to traverse the data.

In preorder traversal, first, root node is visited, then left sub-tree and after that right sub-tree is visited. The process of preorder traversal can be represented as -

Root node is always traversed first in preorder traversal, while it is the last item of postorder traversal. Preorder traversal is used to get the prefix expression of a tree.

The steps to perform the preorder traversal are listed as follows -

• First, visit the root node.
• Then, visit the left subtree.
• At last, visit the right subtree.

The preorder traversal technique follows the Root Left Right policy. The name preorder itself suggests that the root node would be traversed first.

Algorithm

Now, let's see the algorithm of preorder traversal.

Example of preorder traversal

Now, let's see an example of preorder traversal. It will be easier to understand the process of preorder traversal using an example.

The nodes with yellow color are not visited yet. Now, we will traverse the nodes of the above tree using preorder traversal.

• Start with the root node 40. First, print 40 and then recursively traverse the left subtree.
  
• Now, move to the left subtree. For left subtree, the root node is 30. Print 30, and move towards the left subtree of 30.
  
• In left subtree of 30, there is an element 25, so print 25, and traverse the left subtree of 25.
  
• In left subtree of 25, there is an element 15, and 15 has no subtree. So, print 15, and move to the right subtree of 25.
  
• In right subtree of 25, there is 28, and 28 has no subtree. So, print 28, and move to the right subtree of 30.
  
• In right subtree of 30, there is 35 that has no subtree. So print 35, and traverse the right subtree of 40.
  
• In the right subtree of 40, there is 50. Print 50, and traverse the left subtree of 50.
  
• In the left subtree of 50, there is 45 that do not have any child. So, print 45, and traverse the right subtree of 50.
  
• In right subtree of 50, there is 60. Print 60 and traverse the left subtree of 60.
  
• In the left subtree of 60, there is 55 that does not have any child. So, print 55 and move to the right subtree of 60.
  
• In the right subtree of 60, there is 70 that do not have any child. So, print 70 and stop the process.
  

After the completion of preorder traversal, the final output is -

40, 30, 25, 15, 28, 35, 50, 45, 60, 55, 70

Complexity of Preorder traversal

The time complexity of preorder traversal is O(n), where 'n' is the size of binary tree.

Whereas, the space complexity of preorder traversal is O(1), if we do not consider the stack size for function calls. Otherwise, the space complexity of preorder traversal is O(h), where 'h' is the height of the tree.

Implementation of Preorder traversal

Now, let's see the implementation of preorder traversal in different programming languages.

Program: Write a program to implement preorder traversal in C language.

Output

After the execution of the above code, the output will be -

Program: Write a program to implement preorder traversal in C++.

Output

After the execution of the above code, the output will be -

Program: Write a program to implement preorder traversal in C#.

Output

After the execution of the above code, the output will be -

Program: Write a program to implement preorder traversal in Java.

Output

After the execution of the above code, the output will be -

So, that's all about the article. Hope the article will be helpful and informative to you.