## What is Tree Traversal

Tree Traversal is the method in which each node in the tree is visited exactly once in a systematic manner. So to access each node of a tree there are 3 traversal methods such as **Inorder, PreOrder, and PostOrder**.

For instance, you might want to find the sum of all values in the tree or find the largest and smallest value in a tree. For all these operations, you will need to visit each node of the tree.

### Basic Tree Structure

The basic building block of a tree is the Structure, so define a basic structure as a node.

You need to assign a basic data type like int to store the value. Also declare two pointers as *Left and *Right which are the links to the child nodes or links to the left and right subtrees.

```
struct node {
int data;
struct node* left;
struct node* right;
}
```

The struct node pointed to by **left** and **right** might have other left and right children so we should always think of them as sub-trees instead of sub-nodes.

According to this structure, always consider every tree as a combination of a node carrying data and has left and right sub trees.

## Types of Tree Traversal

**In Order****Pre Order****Post Order**

Linear data structures such as Arrays, Linked Lists, Queues, and Stacks have only one pre-determined way to read the data.

But a hierarchical data structure like Trees and graphs can be traversed or visited in different ways.

### In order traversal

Inorder Traversal is one the most used type of DFS **(Depth First Search)** Traversal of the tree.

- First, visit all the nodes in the Left sub tree
- Then visit the Root Node
- Visit all the nodes in the Right sub tree

```
inorder(root->left)
display(root->data)
inorder(root->right)
```

Code language: PHP (php)

### Pre order traversal

- First, Visit the Root Node.
- Then, Visit all the nodes in the Left sub tree
- Visit all the nodes in the Right sub tree

```
display(root->data)
preorder(root->left)
preorder(root->right)
```

Code language: PHP (php)

### Post order traversal

- First, Visit all the nodes in the Left sub tree
- Visit all the nodes in the Right sub tree
- At Last, Visit the Root Node

```
postorder(root->left)
postorder(root->right)
display(root->data)
```

Code language: PHP (php)

## C++ Program Tree Traversal

```
// C++ program tree traversals
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
Node(int data)
{
this->data = data;
left = right = NULL;
}
};
/* postorder traversal. */
void printPostorder(struct Node* node)
{
if (node == NULL)
return;
// first recur on left subtree
printPostorder(node->left);
// then recur on right subtree
printPostorder(node->right);
// now deal with the node
cout << node->data << " ";
}
/* inorder*/
void printInorder(struct Node* node)
{
if (node == NULL)
return;
/* first recur on left child */
printInorder(node->left);
/* then print the data of node */
cout << node->data << " ";
/* now recur on right child */
printInorder(node->right);
}
/* preorder*/
void printPreorder(struct Node* node)
{
if (node == NULL)
return;
/* first print data of node */
cout << node->data << " ";
/* then recur on left sutree */
printPreorder(node->left);
/* now recur on right subtree */
printPreorder(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);
cout << "\nPreorder traversal of binary tree is \n";
printPreorder(root);
cout << "\nInorder traversal of binary tree is \n";
printInorder(root);
cout << "\nPostorder traversal of binary tree is \n";
printPostorder(root);
return 0;
}
```

Code language: PHP (php)