Binary Tree Traversals in C++

Get ready to embark on an exciting journey through the woods — the binary woods, that is. One example of such a task covers the concept of Binary Tree Traversals. A Binary Tree is a type of data structure in which each node has at most two children, referred to as the left child and the right child. Traversing such a structure involves visiting each node in a specific order — and C++, with its powerful features and robust standard library, makes this task quite manageable.

Before diving deeper into the traversals, let's define a simple structure for a binary tree node in C++. Each node in a binary tree will have a value, a reference to its left child, and a reference to its right child.

Here’s how you can define a basic binary tree node class in C++:

#include <iostream>
#include <vector>

class TreeNode {
public:
    int value;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val = 0, TreeNode* leftChild = nullptr, TreeNode* rightChild = nullptr)
        : value(val), left(leftChild), right(rightChild) {}
};

This TreeNode class initializes a node with a given value and optional left and right children, which default to nullptr if not provided. This structure will serve as the foundation for implementing the different binary tree traversal methods.

We have three primary ways to traverse a binary tree: In-order (Left, Root, Right), Pre-order (Root, Left, Right), and Post-order (Left, Right, Root). One way is to use recursive In-order traversal. The algorithm is:

1. Visit the left subtree: If the tree is not empty, recursively perform In-order traversal on the left child.
2. Visit the root node: Process the root node
3. Visit the right subtree: If the tree is not empty, recursively perform an In-order traversal on the right child.

The solution might look like this:

#include <iostream>
#include <vector>

std::vector<int> inorderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return {};
    }
    
    std::vector<int> result;
    std::vector<int> left = inorderTraversal(root->left);
    std::vector<int> right = inorderTraversal(root->right);
    
    result.insert(result.end(), left.begin(), left.end());
    result.push_back(root->value);
    result.insert(result.end(), right.begin(), right.end());
    
    return result;
}

int main() {
    TreeNode* root = new TreeNode(1, nullptr, new TreeNode(2, new TreeNode(3), nullptr));
    std::vector<int> traversalResult = inorderTraversal(root);
    
    for (int val : traversalResult) {
        std::cout << val << " ";
    }
    // Output: 1 3 2
    
    // Free allocated memory
    delete root->right->left;
    delete root->right;
    delete root;

    return 0;
}