Pre-Order Traversal

What is Pre-order Traversal ?  And its implementation   

Traversal

Traversal is a process to all the nodes of a tree. Generally, we traverse a tree to Search or to print all the values it Contains.

Pre-order Traversal

In this method, we visit the node first, then we traverse in left subtree and then we traverse in right subtree. We use recursive method.
So, we visit the root (Visiting means Printing in this context), then we traverse the left subtree recursively. We call Pre-order(left-subtree) and finally we call Pre-order(right-subtree) to traverse the right-subtree.

Algorithm

Step 1 : Visit the root node. we will print value here.

Step 2 : Recursively traverse the left-subtree till it reach the leaf. Do this by calling function Pre-order(left-subtree).

Step 3 : Recursively traverse the right-subtree till it reach the leaf. Do this by calling Pre-order(right-subtree).

Note : Here Pre-order(left-subtree) calls again Pre-order(left-subtree) and Pre-order(right-subtree) it goes until node null.
Do this until all the nodes are traversed and printed.

Example

Figure : Binary tree

Figure : Pre-order applied on binary tree

In this diagram, Algorithm starts with A prints it, then goes to left subtree that is B node prints it then D and it reaches F (left most node or subtree) prints it, then goes to the right-subtree. This process goes on until all the nodes are visited.

Output : A -> B -> D -> F -> G -> E -> C -> H -> I

C++ Program

/* Code for Pre-order Traversal*/
#include <stdio.h>
#include <stdlib.h>
 
/* implementation of the binary tree with pointers to left child node and right child node*/
struct node
{
     char data;
     struct node* left;
     struct node* right;
};
/*In this function we are creating a node with the given data and null left and right pointers  */ 
struct node* CreateNewNode(char data)
{
     struct node* node = (struct node*)
                                  malloc(sizeof(struct node));
     node->data = data;
     node->left = NULL;
     node->right = NULL;
     return(node);
}
/*This is the recursive function for Preorder traversal*/
void PreorderTraversal(struct node* node)
{
     if (node == NULL)
          return;
     printf("%c ", node->data); /*printing data of the node*/
     PreorderTraversal(node->left);/*Recrsion on Left sub-tree*/
     PreorderTraversal(node->right); /*Recursion on Right sub-tree*/
     
}
     
/*main fuction to test the code*/
int main()
{
     /*Here we are creating a tree by inserting elements*/
     /*This is the implementation of tree given in the above example*/
     struct node *root  = CreateNewNode('A');
     root->left             = CreateNewNode('B');
     root->right           = CreateNewNode('C');
     root->right->left     = CreateNewNode('H');
     root->right->right      = CreateNewNode('I');
     root->left->left     = CreateNewNode('D');
     root->left->left->left     = CreateNewNode('F');
     root->left->left->right     = CreateNewNode('G');
     root->left->right   = CreateNewNode('E'); 
     
     printf("Pre-order traversal of the given input binary tree is : \n" );
     PreorderTraversal(root);  
     return 0;
}
Try It

Time complexity : O(n)
Let Complexity function be : C(n)

Number of nodes one side of the root be m So,
C(n) = C(m) + C(n-m-1)

Case 1 :

If m = 0,
C(n) = C(0) + C(n-1) + c
We know, C(n-1) = C(0) + C(n-2) + c
Therefore,
C(n) = 2C(0) + C(n-2) + 2c
C(n) = 3C(0) + C(n-3) + 3c
C(n) =  4C(0) + C(n-4) + 4c
….…………………………………
C(n) = nC(0) + nc
C(n) = n(c + C(0))
C(0) will be some constant p
C(n) = n(c + p)
C(n) =Θ(n) (Theta of n)

Case 2 :

If left and right have equal number of nodes, then
C(n) = 2 X C(n/2) + c
By using master theorem ,
We get C(n) = Θ(n)

Space Complexity

O(h)
h = Height of the tree


Next > < Prev
Scroll to Top