Recusrive Traversal Patterns

Recursive implmeentations follow the core principle of processing the root node before/after children.

Preorder Trvaersal (Root-Left-Right)

class Solution {
public:
    void processNode(TreeNode* current, std::vector<int>& output) {
        if (!current) return;
        output.push_back(current->val);    // Root
        processNode(current->left, output); // Left
        processNode(current->right, output); // Right
    }
    
    std::vector<int> preorder(TreeNode* root) {
        std::vector<int> result;
        processNode(root, result);
        return result;
    }
};

Inorder Traversal (Left-Root-Right)

void processNode(TreeNode* current, std::vector<int>& output) {
    if (!current) return;
    processNode(current->left, output); // Left
    output.push_back(current->val);    // Root
    processNode(current->right, output); // Right
}

Postorder Traversal (Left-Right-Root)

void processNode(TreeNode* current, std::vector<int>& output) {
    if (!current) return;
    processNode(current->left, output); // Left
    processNode(current->right, output); // Right
    output.push_back(current->val);    // Root
}

Iterative Implementations

Preorder (Root-Right-Left Stack Pattern)

std::vector<int> preorderTraversal(TreeNode* root) {
    std::stack<TreeNode*> traversalStack;
    std::vector<int> result;
    if (!root) return result;
    
    traversalStack.push(root);
    while (!traversalStack.empty()) {
        TreeNode* node = traversalStack.top();
        traversalStack.pop();
        result.push_back(node->val);
        
        if (node->right) traversalStack.push(node->right);
        if (node->left) traversalStack.push(node->left);
    }
    return result;
}

Inorder (Left-Root-Right with Stack)

std::vector<int> inorderTraversal(TreeNode* root) {
    std::vector<int> result;
    std::stack<TreeNode*> nodeStack;
    TreeNode* current = root;
    
    while (current || !nodeStack.empty()) {
        if (current) {
            nodeStack.push(current);
            current = current->left;
        } else {
            current = nodeStack.top();
            nodeStack.pop();
            result.push_back(current->val);
            current = current->right;
        }
    }
    return result;
}

Postorder (Reversed Root-Right-Left)

std::vector<int> postorderTraversal(TreeNode* root) {
    std::stack<TreeNode*> traversalStack;
    std::vector<int> result;
    if (!root) return result;
    
    traversalStack.push(root);
    while (!traversalStack.empty()) {
        TreeNode* node = traversalStack.top();
        traversalStack.pop();
        result.push_back(node->val);
        
        if (node->left) traversalStack.push(node->left);
        if (node->right) traversalStack.push(node->right);
    }
    std::reverse(result.begin(), result.end());
    return result;
}

Unified Iterative Pattern

Preorder Implementation

std::vector<int> preorderTraversal(TreeNode* root) {
    std::vector<int> result;
    std::stack<TreeNode*> traversalStack;
    if (root) traversalStack.push(root);
    
    while (!traversalStack.empty()) {
        TreeNode* node = traversalStack.top();
        if (node) {
            traversalStack.pop();
            if (node->right) traversalStack.push(node->right);
            if (node->left) traversalStack.push(node->left);
            traversalStack.push(node);
            traversalStack.push(nullptr);
        } else {
            traversalStack.pop();
            node = traversalStack.top();
            traversalStack.pop();
            result.push_back(node->val);
        }
    }
    return result;
}

Level Order Traversal (Breadth-First)

std::vector<std::vector<int>> levelOrder(TreeNode* root) {
    std::vector<std::vector<int>> result;
    if (!root) return result;
    
    std::queue<TreeNode*> traversalQueue;
    traversalQueue.push(root);
    
    while (!traversalQueue.empty()) {
        int levelSize = traversalQueue.size();
        std::vector<int> currentLevel;
        
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* node = traversalQueue.front();
            traversalQueue.pop();
            currentLevel.push_back(node->val);
            
            if (node->left) traversalQueue.push(node->left);
            if (node->right) traversalQueue.push(node->right);
        }
        result.push_back(currentLevel);
    }
    return result;
}