Binary Tree Preorder Traversal

Intuitionthe traversal order is already the algorithm

Preorder traversal has a fixed contract: record the current node, completely visit its left subtree, then completely visit its right subtree. The recursive solution follows this definition line by line, because each subtree is itself another binary tree that needs the same instruction.

An explicit stack can simulate those recursive calls. When you remove a node from the stack, record it immediately, then put its right child on the stack before its left child. The stack is last-in, first-out, so the left child comes out first and the root-left-right order is preserved.

Approach

1. 1Create an empty result vector and an empty stack of tree-node pointers, because the result must collect values in traversal order while the stack remembers nodes whose turn has not arrived.
2. 2Push the root only when it is non-null, because an empty tree has no node to process and pushing a null pointer would make the first pop invalid.
3. 3While the stack is not empty, pop its top node, because that node is the next recursive call that would have been resumed.
4. 4Append the popped node's value to the result before handling either child, because preorder records the root of each subtree first.
5. 5Push the right child when it exists, because it must wait until the left subtree is finished.
6. 6Push the left child when it exists, because it must sit above the right child and therefore be processed next.
7. 7Return the result after the stack is empty, because every reachable node has then been popped and recorded exactly once.

Complexitycounting nodes and pending work

Annotated solutionC++ · iterative · explicit stack simulation

#include <vector>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* l, TreeNode* r) : val(x), left(l), right(r) {}
};

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> stk;
        if (root) stk.push(root);

        while (!stk.empty()) {
            TreeNode* node = stk.top();
            stk.pop();
            result.push_back(node->val);

            if (node->right) stk.push(node->right);
            if (node->left) stk.push(node->left);
        }

        return result;
    }
};

The two child pushes are the key placement in the solution. The stack does not know that preorder prefers the left subtree; it only knows that its most recently pushed item comes out first. Pushing right first and left second converts that last-in, first-out behavior into the required left-before-right traversal.

The recursive alternativethe definition is shorter, while the call stack stores the pending work

#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* l, TreeNode* r) : val(x), left(l), right(r) {}
};

class Solution {
    void walk(TreeNode* node, vector<int>& result) {
        if (!node) return;
        result.push_back(node->val);
        walk(node->left, result);
        walk(node->right, result);
    }

public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        walk(root, result);
        return result;
    }
};

This is a different arrangement, not an asymptotic optimisation. Both versions take O(n) time and use O(h) working space, with h becoming n for a one-sided tree. Recursion is usually easier to recognise and write, while the explicit stack gives you direct control over pending work and avoids depending on the runtime call stack.

Common mistakesthe two order and empty-tree traps