Binary Tree Preorder Traversal — Editorial

Opening the reading…

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.

The stack reverses the order in which child pointers are pushed.

Approach

Create 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.

Push 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.

While the stack is not empty, pop its top node, because that node is the next recursive call that would have been resumed.

Append the popped node's value to the result before handling either child, because preorder records the root of each subtree first.

Push the right child when it exists, because it must wait until the left subtree is finished.

Push the left child when it exists, because it must sit above the right child and therefore be processed next.

Return the result after the stack is empty, because every reachable node has then been popped and recorded exactly once.

Complexitycounting nodes and pending work

MEASURE	BOUND	WHY
Time	O(n)	Each node is pushed at most once, popped once, and has its value appended once. The stack never causes a node to be revisited, so the total number of operations grows with the number of nodes rather than with the number of possible paths.
Space	O(n) extra, O(h) stack space at a time	The returned vector is required output and is excluded from extra space. The working stack contains at most O(h) pending nodes for a balanced traversal, but a tree shaped as a long chain can make h equal to n, so the worst-case extra space is O(n).

Here, n is the number of nodes and h is the tree height; for this problem n is at most 100.

Annotated solutionC++ · iterative · explicit stack simulation

CPPPop the next node, record it, then push right before left.

#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

CPPThe recursive version mirrors root-left-right directly.

#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.