by Jasleen Chhabra | Updated on 24 August 2024

Tree traversal refers to the process of visiting all the nodes in a tree data structure in a specific order. This is essential for operations such as searching, inserting, and deleting nodes, as well as for various applications like printing tree contents, evaluating expressions, or implementing algorithms. There are several methods for traversing trees, each with its own order and purpose. The three primary types of tree traversal are:

1. In-order Traversal
2. Pre-order Traversal
3. Post-order Traversal

---

1. In-order Traversal

In-order traversal visits nodes in the following order: Left Subtree → Root Node → Right Subtree. This traversal is particularly useful for binary search trees because it retrieves the nodes in sorted order.

Algorithm for In-order Traversal

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

Implementation in C++

Here’s a C++ implementation of in-order traversal for a binary tree:

#include <iostream>

 

struct Node {

    int data;

    Node* left;

    Node* right;

 

    Node(int value) : data(value), left(nullptr), right(nullptr) {}

};

 

void inOrderTraversal(Node* root) {

    if (root == nullptr) return;

 

    inOrderTraversal(root->left);   // Visit left subtree

    std::cout << root->data << " ";  // Visit root

    inOrderTraversal(root->right);  // Visit right subtree

}

 

int main() {

    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);

 

    std::cout << "In-order Traversal: ";

    inOrderTraversal(root);

    std::cout << std::endl;

 

    return 0;

}

---

2. Pre-order Traversal

Pre-order traversal visits nodes in the following order: Root Node → Left Subtree → Right Subtree. This method is useful for creating a copy of the tree or for prefix expression evaluation.

Algorithm for Pre-order Traversal

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

Implementation in C++

Here’s a C++ implementation of pre-order traversal for a binary tree:

#include <iostream>

 

void preOrderTraversal(Node* root) {

    if (root == nullptr) return;

 

    std::cout << root->data << " ";  // Visit root

    preOrderTraversal(root->left);    // Visit left subtree

    preOrderTraversal(root->right);   // Visit right subtree

}

 

int main() {

    // Same tree structure as above

    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);

 

    std::cout << "Pre-order Traversal: ";

    preOrderTraversal(root);

    std::cout << std::endl;

 

    return 0;

}

---

3. Post-order Traversal

Post-order traversal visits nodes in the following order: Left Subtree → Right Subtree → Root Node. This method is useful for deleting a tree or evaluating postfix expressions.

Algorithm for Post-order Traversal

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

Implementation in C++

Here’s a C++ implementation of post-order traversal for a binary tree:

#include <iostream>

 

void postOrderTraversal(Node* root) {

    if (root == nullptr) return;

 

    postOrderTraversal(root->left);   // Visit left subtree

    postOrderTraversal(root->right);  // Visit right subtree

    std::cout << root->data << " ";   // Visit root

}

 

int main() {

    // Same tree structure as above

    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);

 

    std::cout << "Post-order Traversal: ";

    postOrderTraversal(root);

    std::cout << std::endl;

 

    return 0;

}

---

Conclusion

Tree traversal is a fundamental operation in tree data structures, and understanding the different traversal methods is crucial for effectively working with trees. Each traversal method has its specific use cases, and they form the backbone for many algorithms and data structure operations.

By mastering these traversal techniques, you will be better equipped to handle a wide range of problems related to tree data structures in your programming endeavors.