# Tree Traversal – inorder, preorder, and postorder (With Code in C++/Python/Java) Tree traversal is the process of visiting (checking and/or updating) each node in a tree data structure, exactly once, in a specific order.

There are three common ways to traverse a tree:

• In-order traversal
• pre-order traversal
• post-order traversal

## In-order traversal

In-order traversal visits the nodes of a tree in the following order: left subtree, root, right subtree.

### Algorithm

Here is the algorithm for in-order traversal:

1. Traverse the left subtree by calling the in-order function on the root of the left subtree.
2. Visit the root node.
3. Traverse the right subtree by calling the in-order function on the root of the right subtree.

### Example

Here is an example of in-order traversal on the following tree:

``````       1
/   \
2     3
/ \   / \
4   5 6   7``````

The in-order traversal would visit the nodes in the following order: 4, 2, 5, 1, 6, 3, 7.

### Code

Here is some example code for in-order traversal in Python:

``````def in_order_traversal(node):
if node is not None:
in_order_traversal(node.left)
print(node.value)
in_order_traversal(node.right)``````

Here is some example code for in-order traversal in C++:

``````void in_order_traversal(Node *node) {
if (node != nullptr) {
in_order_traversal(node->left);
cout << node->value << " ";
in_order_traversal(node->right);
}
}``````

Here is some example code for in-order traversal in Java:

``````public static void inOrderTraversal(Node node) {
if (node != null) {
inOrderTraversal(node.left);
System.out.print(node.value + " ");
inOrderTraversal(node.right);
}
}``````

## Pre-order traversal

Pre-order traversal visits the nodes of a tree in the following order: root, left subtree, and right subtree.

### Algorithm

Here is the algorithm for in-order traversal:

1. Traverse the left subtree by calling the in-order function on the root of the left subtree.
2. Visit the root node.
3. Traverse the right subtree by calling the in-order function on the root of the right subtree.

### Example

Here is an example of in-order traversal on the following tree:

``````       1
/   \
2     3
/ \   / \
4   5 6   7
``````

The pre-order traversal would visit the nodes in the following order: 1, 2, 4, 5, 3, 6, 7.

### Code

Here is some example code for pre-order traversal in Python:

``````def pre_order_traversal(node):
if node is not None:
print(node.value)
pre_order_traversal(node.left)
pre_order_traversal(node.right)
``````

Here is some example code for pre-order traversal in C++:

``````void pre_order_traversal(Node *node) {
if (node != nullptr) {
cout << node->value << " ";
pre_order_traversal(node->left);
pre_order_traversal(node->right);
}
}``````

Here is some example code for pre-order traversal in Java:

``````public static void preOrderTraversal(Node node) {
if (node != null) {
System.out.print(node.value + " ");
preOrderTraversal(node.left);
preOrderTraversal(node.right);
}
}``````

## Post-order traversal

Post-order traversal visits the nodes of a tree in the following order: left subtree, right subtree, root.

### Algorithm

Here is the algorithm for post-order traversal:

1. Traverse the left subtree by calling the post-order function on the root of the left subtree.
2. Traverse the right subtree by calling the post-order function on the root of the right subtree.
3. Visit the root node.

### Example

Here is an example of post-order traversal on the following tree:

``````       1
/   \
2     3
/ \   / \
4   5 6   7``````

The post-order traversal would visit the nodes in the following order: 4, 5, 2, 6, 7, 3, 1.

### Code

Here is some example code for post-order traversal in Python:

``````def post_order_traversal(node):
if node is not None:
post_order_traversal(node.left)
post_order_traversal(node.right)
print(node.value)``````

Here is some example code for post-order traversal in C++:

``````void post_order_traversal(Node *node) {
if (node != nullptr) {
post_order_traversal(node->left);
post_order_traversal(node->right);
cout << node->value << " ";
}
}``````

Here is some example code for post-order traversal in Java:

``````public static void postOrderTraversal(Node node) {
if (node != null) {
postOrderTraversal(node.left);
postOrderTraversal(node.right);
System.out.print(node.value + " ");
}
}``````