Constructing recursive tree traversal algorithms follows a standardized three-phase design pattern. First, establish the function signature by defining the node input and the container that will store traversal results. Second, define the termination condition to halt recursion when a leaf boundary is reached, usually by validating against a null reference. Third, implement the per-call execution block that handles the current node and delegates control to child subtrees.

Preorder Traversal Implementation

Preorder traversal follows a root-left-right execution sequence. The current node is processed immediately before descending into its children. The implementation below utilizes a private helper method to manage state isolation, separating the recursion mechanics from the public interface.

#include <vector>

class BinarySearchTreeProcessor {
public:
    std::vector<int> executePreorder(TreeNode* rootNode) {
        std::vector<int> traversalRecord;
        if (rootNode != nullptr) {
            traversePre(rootNode, traversalRecord);
        }
        return traversalRecord;
    }

private:
    void traversePre(TreeNode* activeNode, std::vector<int>& sequence) {
        if (activeNode == nullptr) return;
        
        sequence.push_back(activeNode->val);
        traversePre(activeNode->left, sequence);
        traversePre(activeNode->right, sequence);
    }
};

Inorder and Postorder Variants

The traversal behavior is entirely dictated by where the node value is appended relative to the recursive calls. Shifting the append operation between the left and right recursion yields an inorder (left-root-right) traversal.

void traverseIn(TreeNode* activeNode, std::vector<int>& sequence) {
    if (activeNode == nullptr) return;
    
    traverseIn(activeNode->left, sequence);
    sequence.push_back(activeNode->val);
    traverseIn(activeNode->right, sequence);
}

Conversely, placing the append operation after both recursive branches produces a postorder (left-right-root) traversal, ensuring all descendants are recorded before the parent node.

void traversePost(TreeNode* activeNode, std::vector<int>& sequence) {
    if (activeNode == nullptr) return;
    
    traversePost(activeNode->left, sequence);
    traversePost(activeNode->right, sequence);
    sequence.push_back(activeNode->val);
}

These recursive patterns directly map to standard algorithmic assessments, including LeetCode problem 144 for preorder, problem 94 for inorder, and problem 145 for postorder traversal.