Home » C++ programming language

Implement pre-order traversal using C++ program

In this tutorial, we will learn how to implement pre-order traversal using C++ program? This tutorial also contains different methods, algorithms, and examples. By Shubham Singh Rajawat Last updated : August 09, 2023

Pre-order traversal

In pre-order traversal the root is first to be traversed then the left subtree and later the right subtree i.e. in the order NLR (Node Left Right) where Node is the current node.

Here,

• N (process node i.e. current root)
• L (recursively traverse left subtree)
• R (recursively traverse right subtree)

A pre-order traversal can be done in two ways:

1. by recursive method

Algorithm:

preorder(root)
    c. visit the root    
    a. Traverse the left subtree (preorder(root->left))
    b. Traverse the right subtree (preorder(root->right))

2. by non recursive method

This method is implemented by the use of stack.

a. push the root into the stack
b. repeat while stack is not empty
    1. pop an node from the stack and print it
    2. push right child and then left child of the node into the stack 

C++ code to implement pre-order traversal

#include <iostream>
#include <stack>
using namespace std;

/*structure to store a BST*/
struct node {
    int info;
    node *left, *right;
};

/*Method to create a newNode if a tree does not exist*/
node* newNode(int n)
{
    node* ptr = new node;
    ptr->info = n;
    ptr->left = ptr->right = NULL;
    return ptr;
}

/*Method to insert given node in the BST */
node* insert(node* node, int info)
{
    if (node == NULL) {
        return newNode(info);
    }
    if (info < node->info) {
        node->left = insert(node->left, info);
    }
    else {
        node->right = insert(node->right, info);
    }
    return node;
}

/*Method to print preorder traversal of a BST*/
void preorder(node* root)
{
    if (root == NULL) {
        return;
    }

    stack<node*> stack;
    stack.push(root);
    while (!stack.empty()) {
        node* curr = stack.top();
        cout << curr->info << " ";
        stack.pop();

        if (curr->right) {
            stack.push(curr->right);
        }
        if (curr->left) {
            stack.push(curr->left);
        }
    }
}
int main()
{
    node* root = newNode(60);
    insert(root, 50);
    insert(root, 70);
    insert(root, 40);
    insert(root, 30);
    insert(root, 80);
    insert(root, 75);
    insert(root, 65);
    insert(root, 45);
    insert(root, 55);
    insert(root, 90);
    insert(root, 67);

    cout << "Preorder traversal :";
    /*Call/invoke statement for preorder method*/
    preorder(root);

    cout << endl;
    return 0;
}

Output

Preorder traversal :60 50 40 30 45 55 70 65 67 80 75 90