Preorder Traversal – All That You Need To Know

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.

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:

•  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.

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

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

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

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

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

Code: RECURSIVE CODE

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