Every recursive tree traversal follows a consistent decomposition built from three parts: a function signature that accepts the current subtree and an output collector, a base case that stops descent, and the logic that treats each deeper call as already completed.

Recursive Depth-First Traversal

The helper below takes the current node and a reference to a vector. No return value is needed because results are appended in place.

void traverse(TreeNode* current, vector<int>& output) {
    if (!current) return;
    output.push_back(current->val);       // visit root
    traverse(current->left, output);      // explore left
    traverse(current->right, output);     // explore right
}

The base case halts when current is null. Reordering the three body statements yields inorder or postorder without changing anything else.

Iterative Traversal with an Explicit Stack

Preorder traversal processes the root before its children. A stack simulates the call stack by pushing the root, then repeatedly popping the top element, recording its value, and pushing its right child followed by its left child. Because the stack is LIFO, the left child is processed first.

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> output;
    if (!root) return output;
    stack<TreeNode*> pending;
    pending.push(root);
    while (!pending.empty()) {
        TreeNode* current = pending.top();
        pending.pop();
        output.push_back(current->val);
        if (current->right) pending.push(current->right);
        if (current->left)  pending.push(current->left);
    }
    return output;
}

Inorder traversal requires a pointer to walk the left spine. Descend as far left as possible while pushing nodes onto the stack. When the left edge ends, pop the stack—this node is the next in sequence—record it, then move to its right child and repeat.

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

Postorder traversal can be derived from a modified preorder. Collect values in root-right-left order by pushing the left child before the right, then reverse the collection to obtain the standard left-right-root sequence.

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

Unified Iterative Style with Markers

A single framework handles all three depth-first orders by pushing a null marker after a node to indicate it is ready to be recorded. The order in which children and the marker are inserted determines the traversal type.

For inorder, the stack receives the right subtree, the node itself, a null marker, and finally the left subtree. When the marker surfaces, the node immediately below it is recorded.

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> output;
    stack<TreeNode*> pending;
    if (root) pending.push(root);
    while (!pending.empty()) {
        TreeNode* current = pending.top();
        if (current) {
            pending.pop();
            if (current->right) pending.push(current->right);
            pending.push(current);
            pending.push(nullptr);
            if (current->left) pending.push(current->left);
        } else {
            pending.pop();
            current = pending.top();
            pending.pop();
            output.push_back(current->val);
        }
    }
    return output;
}

Adapting this to preorder places the marker after the node but above both children, ensuring the node is recorded before any subtree expansion.

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> output;
    stack<TreeNode*> pending;
    if (root) pending.push(root);
    while (!pending.empty()) {
        TreeNode* current = pending.top();
        if (current) {
            pending.pop();
            if (current->right) pending.push(current->right);
            if (current->left)  pending.push(current->left);
            pending.push(current);
            pending.push(nullptr);
        } else {
            pending.pop();
            current = pending.top();
            pending.pop();
            output.push_back(current->val);
        }
    }
    return output;
}

For postorder, the node and marker sit beneath both children sothat recording occurs only after the subtrees are fully explored.

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> output;
    stack<TreeNode*> pending;
    if (root) pending.push(root);
    while (!pending.empty()) {
        TreeNode* current = pending.top();
        if (current) {
            pending.pop();
            pending.push(current);
            pending.push(nullptr);
            if (current->right) pending.push(current->right);
            if (current->left)  pending.push(current->left);
        } else {
            pending.pop();
            current = pending.top();
            pending.pop();
            output.push_back(current->val);
        }
    }
    return output;
}

Level-Order Traversal (Breadth-First)

Breadth-first search naturally uses a queue. Enqueue the root, then repeatedly dequeue the front element, record its value, and enqueue its non-null children. Capturing the queue size before processing each level groups values by depth.

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> output;
    if (!root) return output;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int levelSize = q.size();
        vector<int> levelValues;
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* current = q.front();
            q.pop();
            levelValues.push_back(current->val);
            if (current->left)  q.push(current->left);
            if (current->right) q.push(current->right);
        }
        output.push_back(levelValues);
    }
    return output;
}

The same layered result can be produced recursively by carrying the current depth through the call stack. When the depth equals the number of existing rows, a new row is created before the value is stored.

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> output;
        buildLevels(root, 0, output);
        return output;
    }
private:
    void buildLevels(TreeNode* node, int depth, vector<vector<int>>& output) {
        if (!node) return;
        if (output.size() == depth) output.emplace_back();
        output[depth].push_back(node->val);
        buildLevels(node->left,  depth + 1, output);
        buildLevels(node->right, depth + 1, output);
    }
};