Binary Tree Traversals: In-order, Pre-order, and Post-order in C++

Introduction

Tree traversal is the process of visiting all the nodes in a binary tree in a specific order. There are three common types of depth-first traversal:

• In-order Traversal: Traverse the left subtree, visit the root node, and then traverse the right subtree.
• Pre-order Traversal: Visit the root node, traverse the left subtree, and then traverse the right subtree.
• Post-order Traversal: Traverse the left subtree, traverse the right subtree, and then visit the root node.

Program Structure

The program will follow these steps:

1. Define a TreeNode structure to represent nodes in the binary tree.
2. Implement recursive functions for in-order, pre-order, and post-order traversals.
3. Write the main function to create a sample binary tree and test all three traversal algorithms.

Code Implementation

// C++ program to implement in-order, pre-order, and post-order traversals

#include <iostream>
using namespace std;

// Define the structure of a tree node
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    // Constructor to initialize the tree node
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// Function for in-order traversal (left, root, right)
void inOrderTraversal(TreeNode* root) {
    if (root == NULL) return;  // Base case

    // Traverse the left subtree
    inOrderTraversal(root->left);

    // Visit the root node
    cout << root->val << " ";

    // Traverse the right subtree
    inOrderTraversal(root->right);
}

// Function for pre-order traversal (root, left, right)
void preOrderTraversal(TreeNode* root) {
    if (root == NULL) return;  // Base case

    // Visit the root node
    cout << root->val << " ";

    // Traverse the left subtree
    preOrderTraversal(root->left);

    // Traverse the right subtree
    preOrderTraversal(root->right);
}

// Function for post-order traversal (left, right, root)
void postOrderTraversal(TreeNode* root) {
    if (root == NULL) return;  // Base case

    // Traverse the left subtree
    postOrderTraversal(root->left);

    // Traverse the right subtree
    postOrderTraversal(root->right);

    // Visit the root node
    cout << root->val << " ";
}

// Helper function to insert a new node into the binary tree (for testing purposes)
TreeNode* insert(TreeNode* node, int val) {
    if (node == NULL) return new TreeNode(val);  // If the tree is empty, create a new node

    // Otherwise, recursively insert the value into the left or right subtree
    if (val < node->val)
        node->left = insert(node->left, val);
    else
        node->right = insert(node->right, val);

    return node;
}

int main() {
    /* Sample Binary Tree:
              10
            /    \
           5      15
          / \    /  \
         3   7  12   20
    */

    // Create an empty binary tree
    TreeNode* root = NULL;

    // Insert nodes into the binary tree
    root = insert(root, 10);
    root = insert(root, 5);
    root = insert(root, 15);
    root = insert(root, 3);
    root = insert(root, 7);
    root = insert(root, 12);
    root = insert(root, 20);

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

    // Perform pre-order traversal
    cout << "Pre-order Traversal: ";
    preOrderTraversal(root);
    cout << endl;

    // Perform post-order traversal
    cout << "Post-order Traversal: ";
    postOrderTraversal(root);
    cout << endl;

    return 0;
}

Explanation

Let’s break down the program:

1. TreeNode structure: This structure represents a node in the binary tree. Each node stores a value val and pointers to its left and right children.
2. inOrderTraversal function: This function implements the in-order traversal:
   • First, it recursively traverses the left subtree.
   • Then, it visits the root node (printing its value).
   • Finally, it recursively traverses the right subtree.
3. preOrderTraversal function: This function implements the pre-order traversal:
   • First, it visits the root node (printing its value).
   • Then, it recursively traverses the left subtree.
   • Finally, it recursively traverses the right subtree.
4. postOrderTraversal function: This function implements the post-order traversal:
   • First, it recursively traverses the left subtree.
   • Then, it recursively traverses the right subtree.
   • Finally, it visits the root node (printing its value).
5. insert function: This helper function is used to insert nodes into the binary tree by comparing the values and placing nodes in the correct position based on binary search tree properties.

How the Traversals Work

The three traversals visit the nodes of the tree in different orders:

• In-order: This traversal first processes the left subtree, then the root, and finally the right subtree. For a binary search tree, in-order traversal will print the nodes in ascending order.
• Pre-order: This traversal first processes the root, then the left subtree, and finally the right subtree. It is useful for creating a copy of the tree.
• Post-order: This traversal first processes the left subtree, then the right subtree, and finally the root. It is useful for deleting nodes in a tree.

Sample Output

If you run the above program with the provided sample binary tree, the output will be:

In-order Traversal: 3 5 7 10 12 15 20 
Pre-order Traversal: 10 5 3 7 15 12 20 
Post-order Traversal: 3 7 5 12 20 15 10 

The in-order traversal prints the nodes in ascending order, while the pre-order and post-order traversals print the nodes in their respective orders.

Conclusion

In this program, we implemented three different types of depth-first traversals for a binary tree: in-order, pre-order, and post-order. Each traversal follows a specific pattern for visiting the nodes, which can be useful for various tasks like searching, copying, or deleting a tree. The time complexity of each traversal is O(N), where N is the number of nodes in the tree, as each node is visited once.