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.

Tree Traversals - Inorder,Postorder and preorder

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.
Tree TraversalsInorder,Preorder and Postorder in C-1

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 Implementation for various Tree traversals

Run
#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 == NULL)
    return;
  // 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 == NULL)
    return;
  // 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 == NULL)
    return;
  // 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 

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Stacks

  • Introduction to Stack in Data Structure
    Click Here
  • Operations on a Stack
    Click Here
  • Stack: Infix, Prefix and Postfix conversions
    Click Here
  • Stack Representation in –
    C | C++ | Java
  • Representation of a Stack as an Array. –
    C | C++ | Java
  • Representation of a Stack as a Linked List. –
    C | C++ | Java
  • Infix to Postfix Conversion –
    C | C++ | Java
  • Infix to prefix conversion in –
    C | C++ | Java
  • Postfix to Prefix Conversion in –
    C | C++ | Java

Queues

  • Queues in Data Structures (Introduction)
    Click Here
  • Queues Program in C and implementation
    Click Here
  • Implementation of Queues using Arrays | C Program
    Click Here
  • Types of Queues in Data Structure
    Click Here
  • Application of Queue Data Structure
    Click Here
  • Insertion in Queues Program (Enqueuing) –
    C | C++ | Java
  • Deletion (Removal) in Queues Program(Dequeuing) –
    C | C++ | Java
  • Reverse a Queue –
    C | C++ | Java
  • Queues using Linked Lists –
    C | C++ | Java
  • Implement Queue using Stack –
    C | C++ | Java
  • Implement Queue using two Stacks –
    C | C++ | Java

Circular Queues

Priority Queue

  • Application of Priority Queue
  • Priority Queue Example
  • Priority Queue Introduction –
    C | C++ | Java
  • Priority Queue Implementation using Array –
    C | C++ | Java
  • Priority Queue using Linked List –
    C | C++ | Java
  • Priority Queue Insertion and Deletion-
    C | C++ | Java

Stacks

Queues

Circular Queues

Priority Queue

  • Application of Priority Queue
  • Priority Queue Example
  • Priority Queue Introduction – C | C++ | Java
  • Priority Queue Implementation using Array – C | C++ | Java
  • Priority Queue using Linked List – C | C++ | Java
  • Priority Queue Insertion and Deletion- C | C++ | Java