Preorder Traversal – All That You Need To Know

Preorder Traversal – All That You Need To Know

2 mins read304 Views Comment
clickHere
Updated on Dec 22, 2022 18:08 IST

Preorder traversal is an a kind of tree traversal in which the root node is visited first, then the left subtree, and finally the right subtree.

2022_12_MicrosoftTeams-image-213.jpg

But before we begin exploring preorder traversal, let’s discuss what a tree is. A tree is a non-linear data structure that consists of nodes connected by edges. Each node in a tree has two pointers referencing its children. In case of leaf nodes their child pointers are referencing to null.

Let’s understand the terminology used in a tree data structure. In tree data structure we use the following terminology.

  • Root – The first node of a tree data structure is known as root node.
  • Edge- The connecting link between any two nodes is known as edge.
  • Child-  The node which is descendant of any node is called child node. We have left and right child in tree data structure. The one which is left to a node is left child and which is right is a right child.

Here’s the image:

2022_12_tree-1.jpg
  •  8 – root node
  • 3 – left child to root node
  • 10 – right child to root node

Preorder traversal

Traversing in non linear data structures like trees there are many possible traversals. One of the  standard traversals is a preorder traversal.

Steps that follows preorder traversal:

  • Processing the root node.
  • Processing the left sub tree in preorder.
  • Processing the right sub tree in preorder.

Algorithm

Let’s see the algorithm for preorder traversal

  1. Visit the root node.
  2. Traverse through the left sub tree in preorder.
  3. Traverse through the right sub tree preorder.

Start with root node 8 and print 8 at screen and recursively traverse left subtree in the preorder fashion.

2022_12_tree1.jpg

2022_12_tree2-1.jpg

For left subtree root node is 12 so print 12 and traverse left of 12 in preorder fashion

The figure shows Preorder Traversal in a tree data structure.

Now root of left subtree is 16 so print 16 .there is no left subtree for 16 so traverse right subtree of 12.

The figure shows the Preorder Traversal in a tree data structure.

Root of subtree is 21 so print 21 and there is no left and right subtree of 21 so traverse right of 8.

The figure shows the Preorder Traversal in a tree data structure.

The Root of subtree is 46 so print 46 there are no left subtree so traverse right subtree.

The figure shows the Preorder Traversal in a tree data structure.

Root of subtree is 66 so print 66 and there are no left and right subtree. 

Code: RECURSIVE CODE

The figure shows the code.

OUTPUT:

The figure shows the output.

Time complexity:

O(n)

Space Compexity:

O(1) if we dont consider size of stack otherwise it is O(h) where h is the height of binary tree.

Author: K Sai Saran

About the Author

This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio

Comments