Binary Tree Preorder Traversal

EasyTrees · DFS (Pre-order)🧩 Tree DFS LeetCode #144 ↗Updated Oct 30, 2026

Problem

Return the values of a binary tree in pre-order: visit the node itself first, then its entire left subtree, then its entire right subtree (Node → Left → Right).

Input[1,null,2,3]Output[1,2,3]

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

Input[]Output[]

0 ≤ nodes ≤ 100 · -100 ≤ Node.val ≤ 100 · Follow-up: recursion is trivial — do it iteratively.

Try it yourself

Java

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The only hard part of DFS is finding the way back after a left subtree. Recursion and stacks remember it in O(h) memory; Morris instead plants a temporary pointer from the left subtree's rightmost node back to the current node.

PatternTree DFS

Instinct If the answer for a node can be built from the answers of its left and right subtrees, write one recursive function and trust it on the children.

Memory hack Ask the kids, then decide - each child reports up, the parent combines, and a global variable keeps the best "bend" seen so far.

Open the Tree DFS guide →

Approaches

Brute ForceRecursive DFS

Time O(n)Space O(h)

Direct translation of the definition: record the node, recurse left, recurse right. The call stack remembers where to return, using one frame per level of depth h.

Java

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    preorder(root, res);
    return res;
}
private void preorder(TreeNode node, List<Integer> res) {
    if (node == null) return;
    res.add(node.val);       // Node
    preorder(node.left, res);  // Left
    preorder(node.right, res); // Right
}

Clearest code, but O(h) call stack (O(n) when skewed) and not what the follow-up wants.

BetterIterative with Explicit Stack

Time O(n)Space O(h)

Simulate the call stack. Pop a node, record it, then push right before left so that the left child (LIFO) is processed next. The stack holds O(h) nodes.

Java

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        res.add(node.val);
        if (node.right != null) stack.push(node.right); // right first ...
        if (node.left != null) stack.push(node.left);   // ... so left pops first
    }
    return res;
}

Iterative (answers the follow-up, no stack-overflow risk) but still O(h) memory.

OptimalMorris Traversal (Threaded Tree)

Time O(n)Space O(1)

With a left child, find the in-order predecessor pred (rightmost node of the left subtree). If pred.right is empty, record the node, thread pred.right = curr and go left. Meeting the thread again means the left side is done: remove it and go right. Each edge is walked O(1) times.

Java

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    TreeNode curr = root;
    while (curr != null) {
        if (curr.left == null) {
            res.add(curr.val);
            curr = curr.right;
            continue;
        }
        TreeNode pred = curr.left; // rightmost node of the left subtree
        while (pred.right != null && pred.right != curr) pred = pred.right;
        if (pred.right == null) {   // first visit: record, thread, go left
            res.add(curr.val);
            pred.right = curr;
            curr = curr.left;
        } else {                    // back via thread: unthread, go right
            pred.right = null;
            curr = curr.right;
        }
    }
    return res;
}

True O(1) extra space; temporarily modifies the tree but restores it exactly.

Pro tip

Move res.add into the else branch (unthread step) and the same loop becomes Morris in-order.

At a glance

Level	Approach	Time	Space
Brute Force	Recursive DFS	`O(n)`	`O(h)`
Better	Iterative with Explicit Stack	`O(n)`	`O(h)`
Optimal	Morris Traversal (Threaded Tree)	`O(n)`	`O(1)`

Common pitfalls

Stack version: pushing left before right → you get Node-Right-Left order.
Morris: forgetting to remove the thread leaves a corrupted (cyclic) tree.
Morris: recording the node on the second visit (that is in-order, not pre-order).

Interview tips

Write the 4-line recursion first, then convert it to a stack for the follow-up.
Explain why right is pushed first (LIFO).
Mention Morris for O(1) space and note it mutates the tree temporarily.

Pattern

DFS order = when you record the node → pre (before children), in (between), post (after); stack or Morris replace recursion.

My notes saved in this browser