In tree data structures, there are three commonly used types of traversals: pre-order, in-order, and post-order. These traversal techniques define the order in which the nodes of a tree are visited. A tree can be traversed in following ways:

• Inorder Traversal
• Preorder Traversal
• Postorder Traversal

Inorder Traversal in Trees

In-order traversal is a way to visit all the nodes of a tree in a specific order. Traversing a binary tree in in-order means visiting the nodes in the following order:

1. Traverse the left subtree.
2. Visit the root node.
3. Traverse the right subtree.

In-order traversal visits the current node in between its left and right subtrees.

For binary search trees, this traversal results in nodes being visited in ascending order. It is commonly used to retrieve the elements of a tree in sorted order.

Here's an example of in-order traversal of a tree:

The in-order traversal of this tree would result in the following sequence of numbers: 1, 3, 2, 6, 4, 5, 7, 8, 9.

Here the left subtree has root-1 and child-3. Now we go by the rule:root→left subtree which gives us 1 and 3 visited. Mark we still are in the left subtree, so we complete left subtree consisting nodes (1 and 3), we move to the root, which is 2 then right→in right subtree there is 4 as root and 6 as child. We implement the left-root-right rule; here is no left child, mark 4 as visited then 6 visited. Right sub tree done! Thus we continue for the rest of the tree.

C++ implementation for in-order traversal:

#include <iostream>
using namespace std;

struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
};

TreeNode* createNode(int data) {
    TreeNode* newNode = new TreeNode;
    newNode->data = data;
    newNode->left = nullptr;
    newNode->right = nullptr;
    return newNode;
}

void inOrderTraversal(TreeNode* root) {
    if (root != nullptr) {
        inOrderTraversal(root->left);
        cout << root->data << " ";
        inOrderTraversal(root->right);
    }
}

int main() {
    // Create the tree
    TreeNode* root = createNode(5);
    root->left = createNode(2);
    root->right = createNode(8);
    root->left->left = createNode(1);
    root->left->right = createNode(4);
    root->right->left = createNode(7);
    root->right->right = createNode(9);
    root->left->left->left = createNode(3);
    root->left->right->right = createNode(6);

    // Perform in-order traversal
    cout << "In-order traversal: ";
    inOrderTraversal(root);
    cout << endl;

    return 0;
}

Output:

In-order traversal: 3 1 2 4 6 5 7 8 9 

In the above code, the createNode function is defined to create a new node with the given data. It allocates memory for the new node, assigns the data, and initializes the left and right pointers to nullptr. The function then returns the pointer to the newly created node.

The inOrderTraversal function is defined to perform the in-order traversal of the binary tree. It takes a pointer to the root of the tree as a parameter. If the current node is not nullptr, the function recursively calls itself on the left subtree, prints the data of the current node, and then recursively calls itself on the right subtree.

In the main function, the binary tree is created by using the createNode function. Nodes are created one by one and connected to their parent nodes using the left and right pointers. The tree structure in the example is recreated.

After creating the tree, the inOrderTraversal function is called with the root of the tree as the argument. This will traverse the tree in in-order fashion and print the node values.