Tree Traversals: Inorder Postorder Preorder In C++

Tree Traversals: Inorder Postorder Preorder in C++

A tree can be traversed using level order and depth first order. There are three traversals in depth first search – Inorder, Preorder and Postorder. In this article, all the three depth first algorithms are covered.

C++ To Find Tree Traversals

More About Preorder Traversal

  1. Preorder traversal is a depth first algorithm.
  2. We first print the value of the node,them move to the left subtree and finally to the right subtree.
  3. If we need to explore more about the node itself before inspecting its leaves, we use preorder traversal.
  4. Preorder traversal is used to find the prefix expression of an expression tree.

More About Inorder Traversal:

  1. Inorder Traversal is a depth first algorithm.
  2. In Inorder Traversal, we first move to the left subtree, then print the node and finally move to the right subtree.
  3. If you want the orginal sequence or how the tree was made, we use the inorder sequence.
  4.  Inorder Traversal of a binary search tree gives the sequence in non decreasing order.

More About Postorder Traversal:

  1. Postorder traversal is a depth first algorithm.
  2. In postorder traversal, we first move to the left subtree then to the right subtree and finally print the node.
  3. Post order traversal is used when we want to free the nodes of the tree.
  4. It is also used to find the postfix expression.

Algorithm To Find Preorder Traversal:

  1. If root is NULL, return NULL.
  2. Print the node.
  3. Visit left subtree.
  4. Visit right subtree.

Algorithm To Find Inorder Traversal:

  1. If root is NULL, return NULL.
  2. Visit the left subtree.
  3. Print the node.
  4. Visit right subtree.

Algorithm To Find Postorder Traversal:

  1. If root is NULL, return NULL.
  2. Visit the left subtree.
  3. Visit the right subtree
  4. Print the data.

Code:

#include <bits/stdc++.h>
using namespace std;
class Tree {
    public:
        int data;
        Tree* left = NULL,*right = NULL;
        // Constructor initialised
        Tree(int x) {
            data = x;
            left = NULL;
            right = NULL;
        }
};
void preorder_traversal (Tree *root) {
    if (root == NULLreturn;
    // Print the data
    cout << root -> data << ” “;
    // Visit Left subtree
    preorder_traversal(root -> left);
    // Visit right subtree
    preorder_traversal(root -> right);
}
void inorder_traversal (Tree *root) {
    if (root == NULLreturn;
    // Visit Left subtree
    inorder_traversal(root -> left);
    // Print the data
    cout << root -> data << ” “;
    // Visit right subtree
    inorder_traversal(root -> right);
}
void postorder_traversal (Tree *root) {
    if (root == NULLreturn;
    // Visit Left subtree
    postorder_traversal(root -> left);
    // Visit right subtree
    postorder_traversal(root -> right);
    // Print the data
    cout << root -> data << ” “;
}
int main() {
    Tree *root = new Tree(17);
    root -> left = new Tree(10);
    root -> right = new Tree(11);
    root -> left -> left = new Tree(7);
    root -> right -> left = new Tree(27);
    root -> right -> right = new Tree(9);
    cout << “Preorder – “;
    preorder_traversal(root);
    cout << endl;
    cout << “Inorder – “;
    inorder_traversal(root);
    cout << endl;
    cout << “Postorder – “;
    postorder_traversal(root);
    cout << endl;
    return 0;
}

 

Output:

Preorder - 17 10 7 11 27 9 
Inorder - 7 10 17 27 11 9
Postorder - 7 10 27 9 11 17

Time Complexity To Find Tree Traversals in Binary Tree

Time Complexity

O(n)

Space Complexity

O(h)