Recursive mechanisms rely on the system call stack to manage state, storing local variables and return addresses during each call. This behavior can be replicated manually using an explicit stack data structure to perform tree traversals iteratively.

Preorder Traversal

Preorder traversal follows the sequence: Root, Left, Right. To simulate this iteratively, push the root node onto the stack first. When popping nodes, process the current node, then push its children. Since stacks operate on a Last-In-First-Out (LIFO) basis, push the right child before the left child. This ensures the left child is popped and processed before the right child.

class Solution {
public:
    std::vector<int> preorderTraversal(TreeNode* root) {
        std::vector<int> output;
        std::stack<TreeNode*> nodeStack;
        
        if (root == nullptr) return output;
        
        nodeStack.push(root);
        while (!nodeStack.empty()) {
            TreeNode* current = nodeStack.top();
            nodeStack.pop();
            output.emplace_back(current->val);
            
            if (current->right != nullptr) {
                nodeStack.push(current->right);
            }
            if (current->left != nullptr) {
                nodeStack.push(current->left);
            }
        }
        return output;
    }
};

Inorder Traversal

Inorder traversal follows the sequnece: Left, Root, Right. This requires traversing to the deepest left node first. Use a pointer to iterate down the left subtree, pushing each node onto the stack. Once the leftmost node is reached, pop from the stack, process the value, and move the pointer to the right child.

class Solution {
public:
    std::vector<int> inorderTraversal(TreeNode* root) {
        std::vector<int> output;
        std::stack<TreeNode*> nodeStack;
        TreeNode* iterator = root;
        
        while (iterator != nullptr || !nodeStack.empty()) {
            while (iterator != nullptr) {
                nodeStack.push(iterator);
                iterator = iterator->left;
            }
            iterator = nodeStack.top();
            nodeStack.pop();
            output.emplace_back(iterator->val);
            iterator = iterator->right;
        }
        return output;
    }
};

Postorder Traversal

Postorder traversal follows the sequence: Left, Right, Root. A common iterative approach modifies the preorder logic. By changing the push order to Left then Right, the pop order becomes Root, Right, Left. Reversing the resulting collection yields the desired Left, Right, Root sequence.

class Solution {
public:
    std::vector<int> postorderTraversal(TreeNode* root) {
        std::vector<int> output;
        std::stack<TreeNode*> nodeStack;
        
        if (root == nullptr) return output;
        
        nodeStack.push(root);
        while (!nodeStack.empty()) {
            TreeNode* current = nodeStack.top();
            nodeStack.pop();
            output.emplace_back(current->val);
            
            if (current->left != nullptr) {
                nodeStack.push(current->left);
            }
            if (current->right != nullptr) {
                nodeStack.push(current->right);
            }
        }
        std::reverse(output.begin(), output.end());
        return output;
    }
};