There are two kinds of traversal, Breadth First and Depth First.

In this post we will be discussing **Depth First Traversals.**

They are of 3 types:

- Preorder
- Inorder
- Postorder

**PreOrder Tree Traversal**

Here we follow this approach

- If root is NULL then return.
- Print the root node.
- Call the recursion on left child of root.
- Call the recursion on right child of root.

Example

Pre-order: F, B, A, D, C, E, G, I, H

**InOrder Tree Traversal**

Here we follow this approach

- If root is NULL then return.
- Call the recursion on left child of root.
- Print the root node.
- Call the recursion on right child of root.

Example

In-order: A, B, C, D, E, F, G, H, I

**PostOrder Tree Traversal**

Here we follow this approach

- If root is NULL then return.
- Call the recursion on left child of root.
- Call the recursion on right child of root.
- Print the root node.

Example

Post-order: A, C, E, D, B, H, I, G, F

Here is the C++ Implementation of the same for Integer nodes for the given tree is :

#include <bits/stdc++.h> using namespace std; struct node { int data; node *left; node *right; }; node * newNode(int a) { node *x=new node; x->data=a; x->left=NULL; x->right=NULL; return x; } void Inorder(node * root) { if(!root) return; Inorder(root->left); cout<<root->data<<" "; Inorder(root->right); } void Preorder(node * root) { if(!root) return; cout<<root->data<<" "; Preorder(root->left); Preorder(root->right); } void Postorder(node * root) { if(!root) return; Postorder(root->left); Postorder(root->right); cout<<root->data<<" "; } int main() { node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); cout<<"Preorder traversal of binary tree is \n"; Preorder(root); cout<<"\nInorder traversal of binary tree is \n"; Inorder(root); cout<<"\nPostorder traversal of binary tree is \n"; Postorder(root); return 0; }

** Time Complexity: **O(n) // as all the nodes are visited once, where n is the number of nodes in the tree

**Output:**

Preorder traversal of binary tree is 1 2 4 5 3 Inorder traversal of binary tree is 4 2 5 1 3 Postorder traversal of binary tree is 4 5 2 3 1