# Binary Tree Traversal | Inorder, Preorder and Postorder

Binary tree traversal can be done in the following ways.

• Inorder traversal
• Preorder traversal
• postorder traversal

Consider the given binary tree,

Inorder Traversal: 7 9 4 2 5 1 3 6 8

Preorder Traversal: 1 2 4 7 9 5 3 6 8

Postorder Traversal: 9 7 4 5 2 8 6 3 1

Inorder Traversal: For binary search trees (BST), Inorder Traversal specifies the nodes in non-descending order. In order to obtain nodes from BST in non-increasing order, a variation of inorder traversal may be used where inorder traversal is reversed.

Preorder Traversal: Preorder traversal will create a copy of the tree. Preorder Traversal is also used to get the prefix expression of an expression.

Postorder Traversal: Postorder traversal is used to get the postfix expression of an expression giv

## Algorithm for binary tree traversal

Inorder(root)

• Traverse the left sub-tree, (recursively call inorder(root -> left).
• Visit and print the root node.
• Traverse the right sub-tree, (recursively call inorder(root -> right).

Preorder(root)

• Visit and print the root node.
• Traverse the left sub-tree, (recursively call inorder(root -> left).
• Traverse the right sub-tree, (recursively call inorder(root -> right).

Postorder(root)

• Traverse the left sub-tree, (recursively call inorder(root -> left).
• Traverse the right sub-tree, (recursively call inorder(root -> right).
• Visit and print the root node.

Program for binary tree traversals in inorder, preorder, and postorder traversals is given below.

`#include <iostream>#include <stdlib.h>using namespace std;/* Structure for a node */struct node{int data;struct node *left;struct node *right;};/* Function to create a new node */struct node *newNode(int data){struct node *temp = (struct node *) malloc(sizeof(struct node));temp -> data = data;temp -> left = NULL;temp -> right = NULL;return temp;};/* Function to insert a node in the tree */void insert_node(struct node *root, int n1, int n2, char lr){if(root == NULL)return;if(root -> data == n1){switch(lr){case 'l' :root -> left = newNode(n2);break;case 'r' : root -> right = newNode(n2);break;}}else{insert_node(root -> left, n1, n2, lr);insert_node(root -> right, n1, n2, lr);}}/* Function to print the inorder traversal of the tree */void inorder(struct node *root){if(root == NULL)return;inorder(root -> left);cout << root -> data << " ";inorder(root -> right);}/* Function to print the preorder traversal of the tree */void preorder(struct node *root){if(root == NULL)return;cout << root -> data << " ";preorder(root -> left);preorder(root -> right);}/* Function to print the postorder traversal of the tree */void postorder(struct node *root){if(root == NULL)return;postorder(root -> left);postorder(root -> right);cout << root -> data << " ";}/* Main Function */int main(){struct node *root = NULL;int n;cout <<"\nEnter the number of edges : ";cin >> n;cout << "\nInput the nodes of the binary tree in order \n\nparent-child-left(or)right-\n\n";while(n--){char lr;int n1,n2;cin >> n1 >> n2;cin >>lr;if(root == NULL){root = newNode(n1);switch(lr){case 'l' :root -> left = newNode(n2);break;case 'r' : root -> right = newNode(n2);break;}}else{insert_node(root,n1,n2,lr);}}cout <<"\nInorder Traversal : ";inorder(root);cout << endl;cout <<"\nPreorder Traversal : ";preorder(root);cout << endl;cout <<"\nPostorder Traversal : ";postorder(root);cout << endl;return 0;}`

Output:

POST A NEW COMMENT

• Input (stdin)

Output (stdout)

Input (stdin)

Expected Output

Compiler Message

Input (stdin)

`2    3`

`5`
`5`
`5`