Given the root of a binary tree, return the preorder traversal of its nodes’ values. Preorder visits: root → left → right.

Examples

Example 1:

Input: root = [1,null,2,3]
    1
     \
      2
     /
    3
Output: [1,2,3]

Example 2:

Input: root = [1,2,3,4,5,null,8,null,null,6,7,null,9]
Output: [1,2,4,5,6,7,3,8,9]

Example 3:

Input: root = []
Output: []

Constraints

  • The number of nodes is in [0, 100]
  • -100 <= Node.val <= 100

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Recursive DFS (this problem) O(n) O(h) stack Natural for trees and graphs
Iterative DFS (stack) O(n) O(n) Avoid recursion depth limits
DFS with memoization O(n) O(n) Overlapping subproblems on graphs
Backtracking DFS O(2^n) typical O(n) Enumerate choices with pruning

Thinking Process

Preorder traversal processes nodes in root → left → right order. Three standard implementations exist:

  1. Recursive – direct translation of the definition
  2. Iterative (stack) – simulate recursion with an explicit stack
  3. Morris traversal – O(1) space using threaded tree

Why Know All Three?

The recursive solution is trivial. Interviewers often follow up with “can you do it iteratively?” or “can you do it in O(1) space?” – that’s where the stack and Morris approaches matter.

Tree DFS (bottom-up) 3 9 20 15 7 post-order: combine left + right + 1

Approach 1: Recursive – O(n)

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> rtn;
        preorder(root, rtn);
        return rtn;
    }

private:
    void preorder(TreeNode* node, vector<int>& rtn) {
        if (!node) return;
        rtn.push_back(node->val);
        preorder(node->left, rtn);
        preorder(node->right, rtn);
    }
};

Solution Explanation

Approach: Recursive DFS (this problem)

Key idea: Preorder traversal processes nodes in root → left → right order. Three standard implementations exist:

How the code works:

  1. Recursive – direct translation of the definition
  2. Iterative (stack) – simulate recursion with an explicit stack
  3. Morris traversal – O(1) space using threaded tree

Walkthrough — input root = [1,null,2,3], expected output [1,2,3]:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

    Approach 2: Iterative (Stack) – O(n)

Push right child first, then left, so left is processed first (LIFO).

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if (!root) return {};
        vector<int> rtn;
        stack<TreeNode*> st;
        st.push(root);

        while (!st.empty()) {
            TreeNode* node = st.top(); st.pop();
            rtn.push_back(node->val);
            if (node->right) st.push(node->right);
            if (node->left) st.push(node->left);
        }

        return rtn;
    }
};

Time: O(n) Space: O(h) for the stack

Approach 3: Morris Traversal – O(n) time, O(n) space

Use the tree’s null pointers to thread back to ancestors, avoiding a stack entirely. For preorder: visit the node before following the thread.

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> rtn;
        TreeNode* cur = root;

        while (cur) {
            if (!cur->left) {
                rtn.push_back(cur->val);
                cur = cur->right;
            } else {
                TreeNode* pred = cur->left;
                while (pred->right && pred->right != cur)
                    pred = pred->right;

                if (!pred->right) {
                    rtn.push_back(cur->val);
                    pred->right = cur;
                    cur = cur->left;
                } else {
                    pred->right = nullptr;
                    cur = cur->right;
                }
            }
        }

        return rtn;
    }
};

Time: O(n) – each edge traversed at most twice Space: O(n) for the output vector; O(1) auxiliary

Comparison

Approach Time Space Notes
Recursive O(n) O(h) Simplest, may stack overflow on deep trees
Iterative Stack O(n) O(h) Common interview follow-up
Morris O(n) O(n) O(1) auxiliary; modifies tree temporarily, restores it

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Key Takeaways

  • All three traversal orders (pre/in/post) share the same three implementation strategies
  • Iterative stack trick for preorder: push right before left so left pops first
  • Morris: useful when O(1) space is required; temporarily modifies the tree but restores it

References

Template Reference