## Algorithm

Tree traversal is a process of visiting and processing each node in a tree data structure. There are three main types of tree traversal: inorder, preorder, and postorder. These terms refer to the order in which the nodes are visited.

1. Inorder Traversal:

• In an inorder traversal, the left subtree is visited first, then the root node, and finally the right subtree.
• The order is Left, Root, Right.

Example:

`makefile`
``````Inorder: 4, 2, 5, 1, 3
1
/ \
2   3
/ \
4   5``````
``` ```
• Preorder Traversal:

• In a preorder traversal, the root node is visited first, followed by the left subtree, and then the right subtree.
• The order is Root, Left, Right.

Example:

`makefile`
``````Preorder: 1, 2, 4, 5, 3
1
/ \
2   3
/ \
4   5``````
• Postorder Traversal:

• In a postorder traversal, the left subtree is visited first, followed by the right subtree, and then the root node.
• The order is Left, Right, Root.

Example:

`makefile`
``````Postorder: 4, 5, 2, 3, 1
1
/ \
2   3
/ \
4   5``````

These traversals are applicable to various types of trees, including binary trees and binary search trees. They are commonly used in algorithms and data structures for tasks such as searching, insertion, and deletion in trees.

## Code Examples

### #1 Tree Traversal - inorder, preorder and postorder implement in Python

```Code - Python Programming```

### #2 Tree Traversal - inorder, preorder and postorder implement in Java

```Code - Java Programming```

``````class TreeNode {
int data;
TreeNode left;
TreeNode right;

public TreeNode(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}

public class TreeTraversal {

// Inorder traversal: left -> root -> right
public static void inorderTraversal(TreeNode root) {
if (root != null) {
inorderTraversal(root.left);
System.out.print(root.data + " ");
inorderTraversal(root.right);
}
}

// Preorder traversal: root -> left -> right
public static void preorderTraversal(TreeNode root) {
if (root != null) {
System.out.print(root.data + " ");
preorderTraversal(root.left);
preorderTraversal(root.right);
}
}

// Postorder traversal: left -> right -> root
public static void postorderTraversal(TreeNode root) {
if (root != null) {
postorderTraversal(root.left);
postorderTraversal(root.right);
System.out.print(root.data + " ");
}
}

public static void main(String[] args) {
// Create a sample binary tree
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

// Perform tree traversals
System.out.println("Inorder traversal:");
inorderTraversal(root);

System.out.println("\nPreorder traversal:");
preorderTraversal(root);

System.out.println("\nPostorder traversal:");
postorderTraversal(root);
}
}
``````
Copy The Code &

### #3 Tree Traversal - inorder, preorder and postorder implement in C

```Code - C Programming```

``````#include <stdio.h>
#include <stdlib.h>

// Definition of a binary tree node
struct Node {
int data;
struct Node* left;
struct Node* right;
};

// Function to create a new node with the given data
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}

// Function for inorder tree traversal
void inorderTraversal(struct Node* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}

// Function for preorder tree traversal
void preorderTraversal(struct Node* root) {
if (root != NULL) {
printf("%d ", root->data);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}

// Function for postorder tree traversal
void postorderTraversal(struct Node* root) {
if (root != NULL) {
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->data);
}
}

int main() {
// Create a sample binary tree
struct Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);

// Perform different tree traversals
printf("Inorder Traversal: ");
inorderTraversal(root);
printf("\n");

printf("Preorder Traversal: ");
preorderTraversal(root);
printf("\n");

printf("Postorder Traversal: ");
postorderTraversal(root);
printf("\n");

return 0;
}
``````
Copy The Code &

### #4 Tree Traversal - inorder, preorder and postorder implement in C++

```Code - C++ Programming```

``````#include <iostream>

// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// Function to perform inorder traversal
void inorderTraversal(TreeNode* root) {
if (root) {
inorderTraversal(root->left);
std::cout << root->val << " ";
inorderTraversal(root->right);
}
}

// Function to perform preorder traversal
void preorderTraversal(TreeNode* root) {
if (root) {
std::cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}

// Function to perform postorder traversal
void postorderTraversal(TreeNode* root) {
if (root) {
postorderTraversal(root->left);
postorderTraversal(root->right);
std::cout << root->val << " ";
}
}

int main() {
// Example usage:
// Creating a sample binary tree
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);

// Inorder traversal: 4 2 5 1 3
std::cout << "Inorder traversal: ";
inorderTraversal(root);
std::cout << std::endl;

// Preorder traversal: 1 2 4 5 3
std::cout << "Preorder traversal: ";
preorderTraversal(root);
std::cout << std::endl;

// Postorder traversal: 4 5 2 3 1
std::cout << "Postorder traversal: ";
postorderTraversal(root);
std::cout << std::endl;

// Clean up memory (optional)
// Note: In a real application, you would need to free the allocated memory.
delete root->left->left;
delete root->left->right;
delete root->left;
delete root->right;
delete root;

return 0;
}
``````
Copy The Code &