Tree Traversals

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.

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

Consider the below tree,

Inorder Traversal

Traverse Left Subtree
Visit Root Node
Traverse Right Subtree

Inorder (Left, Root, Right)

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

Preorder Traversal

Visit Root Node
Traverse Left Subtree
Traverse Right Subtree

Preorder (Root, Left, Right)

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

Postorder Traversal

Traverse Left Subtree
Traverse Right Subtree
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.

Tree Traversals – Preorder, Inorder, Postorder