Preorder, Inorder and Postorder traversals

Tree traversal using preorder, inorder & postorder tree traversals

In Pre-Order tree traversal, the root data is accessed as soon as the root is visited. After the root data is accessed, the left sub-tree of the root node is visited and then the right sub-tree. The traversal is recursive in nature, i.e the left sub-tree and the right sub-tree are traversed similarly to the root.
Example of pre-order traversal of a binary tree : 9, 5, 3, 7, 16, 12, 18

In In-Order tree traversal, the data in left sub-tree is accessed first, followed by the data of the root, followed by the data in the right sub-tree. The traversal is recursive in nature.
Example of an in-order traversal of a binary tree : 3, 5, 7, 9, 12, 16, 18

In Post-Order tree traversal, the data in left sub-tree is accessed first, followed by the data in the right sub-tree, followed by the data in the root. The traversal is recursive in nature.
Example of a post-order traversal of a binary tree : 3, 7, 5, 12, 18, 16, 9

Note: Accessing/Processing the data of a node is different from visiting the node. Tree_Image

Data structure used for pre-order, in-order and post-order traversals : Stack
Time complexity of pre-order, in-order and post-order traversals : O(n), where n is the number of nodes in the graph.


Python

Python : Pre-order, In-order and Post-order tree traversals implementation in Python 3


Java

Java : Pre-order, In-order and Post-order tree traversals implementation in Java 8


C++ : PreOrder, InOrder and PostOrder tree traversals implementation in C++11

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

class Node{

public:

    Node(int n):data(n),left(NULL),right(NULL){
    }   
    Node * left;
    Node * right;
    int data;
};

void PreOrderRecursive(Node * node){

    if (node != NULL) {
        cout << node->data << " ";      // Access the data 
        PreOrderRecursive(node->left);  // Visit current node's left node
        PreOrderRecursive(node->right); // Visit current node's right node
    }   
}

void PreOrder (Node * node) {

    stack<Node*> stk;

    while (node != NULL or !stk.empty()) {

        if (node == NULL) {
            node = stk.top();
            stk.pop();
            node = node->right;
        }

        if (node != NULL) {
            cout << node->data << " ";
            stk.push(node);
            node = node->left;
        }
    }   
}

void InOrderRecursive (Node * node) {

    if (node != NULL) {
        InOrderRecursive(node->left);
        cout << node->data << " ";
        InOrderRecursive(node->right);
    }   
}

void InOrder (Node * node) {

    stack<Node *> stk;

    while (node != NULL or !stk.empty()) {

        if (node == NULL) {
            node = stk.top();
            stk.pop();
            cout << node->data << " ";
            node = node->right;
        }

        if (node != NULL) {
            stk.push(node);
            node = node->left;
        }
    }   
}

void PostOrderRecursive (Node * node) {

    if (node != NULL) {
        PostOrderRecursive(node->left);
        PostOrderRecursive(node->right);
        cout << node->data << " ";
    }
}

void PostOrder (Node * node) {

    stack<Node *> stk_postorder;
    stack<Node *> stk;

    if (node != NULL) {
        stk.push(node);
    }   

    while (!stk.empty()) {

        node = stk.top();
        stk_postorder.push(node);
        stk.pop();

        if (node->left != NULL) {
            stk.push(node->left);
        }

        if (node->right != NULL) {
            stk.push(node->right);
        }
    }   

    while (!stk_postorder.empty()) {
        cout << stk_postorder.top()->data << " ";
        stk_postorder.pop();
    }
}

/* Constructed binary tree is
               9
             /   \
            5     16
          /  \   /  \
         3   7  12   18
*/

int main() {

    Node *root = new Node(9);
    root->left = new Node(5);
    root->right = new Node(16);
    root->left->left  = new Node(3);
    root->left->right = new Node(7);
    root->right->left = new Node(12);
    root->right->right = new Node(18);

    cout << "---- Recursive approach ----" << endl;
    cout << "Pre-Order traversal:  "; PreOrderRecursive(root); cout << endl;
    cout << "In-Order traversal:   "; InOrderRecursive(root); cout << endl;
    cout << "Post-Order traversal: "; PostOrderRecursive(root); cout << endl;

    cout << "---- Stack based approach ----" << endl;
    cout << "Pre-Order traversal:  "; PreOrder(root); cout << endl;
    cout << "In-Order traversal:   "; InOrder(root); cout << endl;
    cout << "Post-Order traversal: "; PostOrder(root); cout << endl;

    // Cleanup
    delete root->right->right;
    delete root->right->left;
    delete root->left->right;
    delete root->left->left;
    delete root->right;
    delete root->left;
    delete root;

    return 0;
}

Output of PreOrder, InOrder and PostOrder tree traversals implemented in C++

---- Recursive approach ----
Pre-Order traversal:  9 5 3 7 16 12 18 
In-Order traversal:   3 5 7 9 12 16 18 
Post-Order traversal: 3 7 5 12 18 16 9 

---- Stack based approach ----
Pre-Order traversal:  9 5 3 7 16 12 18 
In-Order traversal:   3 5 7 9 12 16 18 
Post-Order traversal: 3 7 5 12 18 16 9 

Copyright © 2019-2020, Algotree.org.
All rights reserved.