Preorder Traversal of Binary Trees

In general, Stack, Array, Queue, and other linear data structures only have one way to traverse the data. However, there are numerous ways to traverse through the data in a hierarchical data structure like a tree.

The prototype which the preorder traversal generally follows is, the root node is visited first then the left sub tree of the root node is traversed recursively. Then the right sub tree of the root node is traversed down the tree recursively.

So, the general notation for the preorder traversal is

NLR

Node  Left  Right.

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

The preorder traversal of the binary tree is used to produce the prefix expression of the binary tree.

Algorithm for preorder traversal Technique.

Step 1: Repeat Steps 2 to 4 while TREE != NULL  

Step 2: Write TREE -> DATA  

Step 3: PREORDER (TREE -> LEFT)  

Step 4: PREORDER (TREE -> RIGHT)  

[END OF LOOP]  

#include <stdio.h>  
#include <stdlib.h>  
  
struct node {  
    int element;  
    struct node* left;  
    struct node* right;  
};  
  
/*To create a new node*/  
     struct node* createNode(int val)  
{  
    struct node* Node = (struct node*)malloc(sizeof(struct node));  
    Node->element = val;  
    Node->left = NULL;  
    Node->right = NULL;  
  
    return (Node);  
}  
  
  
/*function to traverse the nodes of binary tree in preorder*/  
void traversePreorder(struct node* root)  
{  
    if (root == NULL)  
        return;  
    printf(" %d ", root->element);  
   raversePreorder(root->left);  
    traversePreorder(root->right);  
}  
  
     int main()  
{  
    struct node* root = createNode(40);  
    root->left = createNode(30);  
    root->right = createNode(50);  
    root->left->left = createNode(25);  
    root->left->right = createNode(35);  
    root->left->left->left = createNode(15);  
    root->left->left->right = createNode(28);  
    root->right->left = createNode(45);  
    root->right->right = createNode(60);  
    root->right->right->left = createNode(55);  
    root->right->right->right = createNode(70);  
      
    printf("\n The Preorder traversal of given binary tree is -\n");  
    traversePreorder(root);  
   return 0;  
   }  

#include <iostream>  
  
using namespace std;  
  
struct node {  
    int element;  
    struct node* left;  
    struct node* right;  
};  
  
/*To create a new node*/  
struct node* createNode(int val)  
{  
    struct node* Node = (struct node*)malloc(sizeof(struct node));  
    Node->element = val;  
    Node->left = NULL;  
    Node->right = NULL;  
  
    return (Node);  
}  
  
  
/*function to traverse the nodes of binary tree in preorder*/  
void traversePreorder(struct node* root)  
{  
    if (root == NULL)  
        return;  
    cout<<" "<<root->element<<" ";  
    traversePreorder(root->left);  
    traversePreorder(root->right);  
}  
  
int main()  
{  
    struct node* root = createNode(39);  
    root->left = createNode(29);  
    root->right = createNode(49);  
    root->left->left = createNode(24);  
    root->left->right = createNode(34);  
    root->left->left->left = createNode(14);  
    root->left->left->right = createNode(27);  
    root->right->left = createNode(44);  
    root->right->right = createNode(59);  
    root->right->right->left = createNode(54);  
    root->right->right->right = createNode(69);  
      
    cout<<"\n The Preorder traversal of given binary tree is -\n";  
    traversePreorder(root);  
    return 0;  
}