inorder, preorder, postorder

Tree Traversals – Preorder, Inorder, Postorder

Tree Traversal: visiting every node of a tree. Unlike other linear data structures, where we traverse through every element in order, it's not the same with the tree. Trees being non-linear data structures, there will always be more than one way to traverse through a tree. There are three types of Tree Traversals namely, Inorder, Preorder, and Postorder. In this post, I'll explain briefly all three methods with code.

Tree Data Structure

A Tree Data Structure contains a root node, and every node can have a left and right child.

Tree

Tree Traversals

  • Inorder (Left, Root, Right)
  • Preorder (Root, Left, Right)
  • Postorder (Left, Right, Root)

Consider the below tree,

Tree

Inorder Traversal

  1. Traverse Left Subtree
  2. Visit Root Node
  3. Traverse Right Subtree
Inorder (Left, Root, Right)

Output: 4->2->5->1->6->3->7

Preorder Traversal

  1. Visit Root Node
  2. Traverse Left Subtree
  3. Traverse Right Subtree
Preorder (Root, Left, Right)

Output: 1->2->4->5->3->6->7

Postorder Traversal

  1. Traverse Left Subtree
  2. Traverse Right Subtree
  3. Visit Root Node
Postorder (Left, Right, Root)

Output:4->5->2->6->7->3->1

Code

#include <iostream>
using namespace std;

struct Node
{
  int data;
  struct Node *left, *right;
  Node(int data)
  {
    this->data = data;
    left = right = NULL;
  }
};

// Preorder traversal
void preorderTraversal(struct Node *node)
{
  if (node == NULL)
    return;
  cout << node->data <<"->";
  preorderTraversal(node->left);
  preorderTraversal(node->right);
}

// Postorder traversal
void postorderTraversal(struct Node *node)
{
  if (node == NULL)
    return;
  postorderTraversal(node->left);
  postorderTraversal(node->right);
  cout << node->data <<"->";
}

// Inorder traversal
void inorderTraversal(struct Node *node)
{
  if (node == NULL)
    return;
  inorderTraversal(node->left);
  cout << node->data <<"->";
  inorderTraversal(node->right);
}

int main()
{
  struct Node *root = new Node(1);
  root->left = new Node(2);
  root->right = new Node(3);
  root->left->left = new Node(4);
  root->left->right = new Node(5);
  root->right->left = new Node(6);
  root->right->right = new Node(7);

  cout <<"Inorder traversal" ;
  inorderTraversal(root);

  cout <<"\nPreorder traversal" ;
  preorderTraversal(root);

  cout <<"\nPostorder traversal" ;
  postorderTraversal(root);
}

Output

Inorder traversal 4->2->5->1->6->3->7->
Preorder traversal 1->2->4->5->3->6->7->
Postorder traversal 4->5->2->6->7->3->1->

Conclusion

This post is a part of my #30DaysChallenge to write a blog post every day on what I learn, Happy Coding~ Abhiram Reddy.

Leave a Reply

Your email address will not be published. Required fields are marked *

Popular posts