# Tree Traversals – Preorder, Inorder, Postorder

• DSA

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 Traversals

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

Consider the below 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.