Free lesson · DSA Mastery - Interview Prep, End to End

Binary Tree Preorder Traversal

Medium8 min readdsabinary-tree

Binary Tree Preorder Traversal

Binary Tree Preorder Traversal opens the Pre Order sub-group with the literal node-left-right traversal: visit the current node first, then recurse into the left subtree, then the right. It's the natural order for problems that build something from the root downward - copying a tree, serializing it, accumulating root-to-node paths, comparing two trees top-down. We present three forms: the trivial recursion, the iterative stack version (which makes the visit order explicit), and Morris traversal (O(1) extra space by temporary threading).

The insight: preorder is defined purely by when you record the node - before descending into either child. The recursion expresses this directly. The iterative version must use a stack and, crucially, push the right child before the left so the left is processed first (a stack reverses order). Morris traversal threads the tree to walk it without any stack at all.

The Problem

Given the root of a binary tree, return the preorder traversal of its nodes' values.

Example 1:

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

Example 2:

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

Example 3:

Input:  root = []
Output: []

Constraints:

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

Follow-up: Recursive solution is trivial, could you do it iteratively?

Approaches Overview

#	Approach	Time	Space	Verdict
1	Recursion	O(n)	O(h)	Simplest
2	Iterative with stack	O(n)	O(h)	Answers the follow-up
3	Morris traversal	O(n)	O(1) extra	Constant space

All visit every node once - O(n). Recursion is trivial but uses O(h) stack. The iterative version uses an explicit stack (also O(h)) and is the expected follow-up answer. Morris threading achieves O(1) extra space by temporarily rewiring pointers, at the cost of more intricate code.

Approach 1: Recursion - Simplest

The Idea

Record the node's value, then recurse left, then recurse right. The "node first" placement is what makes it preorder.

Logic Flowchart

graph TD
    A["preorder(node)"] --> B{"node == null?"}
    B -->|Yes| C["return"]
    B -->|No| D["visit node (record val)"]
    D --> E["preorder(left)"]
    E --> F["preorder(right)"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9

This flowchart shows recursive preorder. We record the current node's value first, then recurse into the left subtree, then the right.

Code

public static List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    preorder(root, result);
    return result;
}

private static void preorder(TreeNode node, List<Integer> result) {
    if (node == null) return;
    result.add(node.val);          // visit node FIRST
    preorder(node.left, result);   // then left
    preorder(node.right, result);  // then right
}

This Java code records the current node's value, then recurses left, then right, producing node-left-right order.

Complexity

Time: O(n). Space: O(h) recursion stack.

Approach 2: Iterative with Stack - Answers the Follow-up

The Idea

Use an explicit stack. Push the root. Repeatedly pop a node, record it, then push its right child and then its left child - so the left is popped (and processed) next. This reproduces node-left-right order. Skip null children.

Logic Flowchart

graph TD
    A["if root null: return []; stack = [root]"] --> B{"stack not empty?"}
    B -->|No| C["return result"]
    B -->|Yes| D["node = pop; result.add(node.val)"]
    D --> E["push right child (if any)"]
    E --> F["push left child (if any)"]
    F --> B

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9

This flowchart shows iterative preorder. We pop a node and record it, then push its right child before its left, so the left child is processed next, reproducing node-left-right order.

Code

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

// Usage:
// preorderTraversal([1,null,2,3]) -> [1,2,3]

This Java code uses a stack. Each popped node is recorded, then its right child is pushed before its left, ensuring the left subtree is processed before the right.

Step-by-Step Walkthrough

A frame-by-frame trace on root = [1,null,2,3] (1 has right child 2; 2 has left child 3):

graph LR
    F0["stack=[1]; pop 1 → result=[1]; push 2 (right). stack=[2]"]
    F1["pop 2 → result=[1,2]; push 3 (left). stack=[3]"]
    F2["pop 3 → result=[1,2,3]; no children. stack empty"]
    F3["return [1,2,3]"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough traverses one with a right child two, which has a left child three. Popping one records it and pushes two; popping two records it and pushes three; popping three records it, giving one, two, three.

Result: [1,2,3].

Complexity

Time: O(n). Space: O(h) stack.

Approach 3: Morris Traversal - Constant Space

The Idea

Morris traversal walks the tree using O(1) extra space by temporarily threading. For each node cur: if it has no left child, record it and move right. Otherwise find its in-order predecessor (rightmost node of the left subtree); if that predecessor's right is null, record cur now (preorder), thread the predecessor's right to cur, and move left; if the predecessor's right already points to cur, the left subtree is done - unthread it and move right. The threading lets you return to ancestors without a stack.

Logic Flowchart

graph TD
    A["cur = root"] --> B{"cur != null?"}
    B -->|No| C["return result"]
    B -->|Yes| D{"cur.left == null?"}
    D -->|Yes| E["record cur; cur = cur.right"]
    D -->|No| F["pred = rightmost of cur.left"]
    F --> G{"pred.right == null?"}
    G -->|Yes| H["record cur (preorder); pred.right = cur; cur = cur.left"]
    G -->|No| I["pred.right = null (unthread); cur = cur.right"]
    E --> B
    H --> B
    I --> B

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style I fill:#b45309,stroke:#f59e0b,color:#f1f5f9

This flowchart shows Morris preorder. For a node with no left child we record it and go right. Otherwise we find its left subtree's rightmost node; if unthreaded, we record the node, thread the predecessor to it, and go left; if already threaded, we unthread and go right.

Code

public static List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left == null) {
            result.add(cur.val);                 // no left subtree: visit, go right
            cur = cur.right;
        } else {
            TreeNode pred = cur.left;
            while (pred.right != null && pred.right != cur) pred = pred.right;
            if (pred.right == null) {
                result.add(cur.val);             // PREORDER: visit before going left
                pred.right = cur;                // thread back to cur
                cur = cur.left;
            } else {
                pred.right = null;               // unthread; left subtree finished
                cur = cur.right;
            }
        }
    }
    return result;
}

This Java code performs Morris preorder. Nodes without a left child are recorded and we move right. Otherwise we thread the left subtree's rightmost node back to the current node, recording the current node before descending left, and unthread when returning.

Complexity

Time: O(n) (each edge traversed a constant number of times). Space: O(1) extra.

Complexity Comparison

Approach	Time	Space	Key Idea	When to Use
Recursion	O(n)	O(h)	Node, then recurse	Simplest
Iterative stack	O(n)	O(h)	Push right before left	Follow-up answer
Morris	O(n)	O(1) extra	Temporary threading	Constant space required

All are O(n) time. Recursion is the cleanest to write; the iterative stack is the standard follow-up answer; Morris is the O(1)-space technique to mention when an interviewer pushes on memory. The stack version's "push right before left" detail is the key trick.

Variations & Follow-ups

Why push the right child before the left in the iterative version?

A stack is last-in-first-out, so the most recently pushed node pops first. To process the left subtree before the right (as preorder requires), you must push the right child first and the left child second - then the left pops next. Pushing in the natural left-then-right order would reverse the traversal, processing the right subtree first. This inversion is the single subtle point of the iterative solution.

How does Morris achieve O(1) space?

Instead of a stack to remember where to return, Morris temporarily sets the in-order predecessor's right pointer to thread back to the current node. When the left subtree finishes, that thread leads back up, and the algorithm removes it (restoring the tree). Because the return path is encoded in the tree itself, no auxiliary stack is needed. Each edge is visited at most a constant number of times, keeping it O(n) time despite the threading.

What's the difference between preorder and the other DFS orders?

All three DFS orders recurse left then right; they differ only in where the "visit node" step sits. Preorder visits before both recursions (node, left, right), inorder visits between them (left, node, right), and postorder visits after both (left, right, node). That single positional choice gives entirely different output orders and suits different problems - preorder for top-down construction, inorder for sorted BST output, postorder for bottom-up aggregation.

When is preorder the right choice for a problem?

Preorder shines when a node's processing must happen before its children's - building a copy or serialization top-down (the root must exist before its subtrees attach), accumulating a path from the root (you extend the path at the node, then descend), or comparing two trees node-by-node from the top. Several upcoming problems (Same Tree, Binary Tree Paths, serialization) are preorder precisely for this reason.

What about edge cases?

Empty tree (Example 3): Empty result.
Single node: [root.val].
Left-skewed chain: Visits top to bottom: [root, child, grandchild, …].
Right-skewed chain: Same order, all via right children.

Common Interview Pitfalls

Pushing left before right in the stack version. Reverses the order; push right first.
Forgetting the empty-tree guard. The iterative version must return early on a null root.
Morris: not unthreading. Failing to restore pred.right = null corrupts the tree and can loop infinitely.
Recording at the wrong time in Morris. Preorder records when creating the thread (before going left), not when removing it.

Why This Topic Matters

Binary Tree Preorder Traversal establishes the node-first DFS order and three ways to realize it - recursion, explicit stack (with the right-before-left trick), and Morris threading for O(1) space. These mechanics underpin every preorder problem that follows, and the "visit before recursing" placement is the defining idea you'll apply to top-down construction, path-building, and tree-comparison problems throughout this sub-group.

The next topic, Same Tree, is the simplest preorder comparison: given two trees, determine whether they are structurally identical with equal node values. The recursion is pure preorder - compare the two current nodes, then recursively compare their left subtrees and their right subtrees - and it cements the "process the node, then recurse" pattern in a two-tree setting that recurs in Symmetric Tree and Subtree of Another Tree.

Back to DSA Mastery - Interview Prep, End to End