Binary Tree Preorder Traversal

EASY✓ CHIP-TIMEDLC #144 — FULL STATEMENT ↗

The drill: Walk a binary tree node, left, right and list every value in that order — the shape you'd read off if you called out each node the moment you arrived at it.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A binary tree arrives, and the task is to list its values by visiting the current node first, then its left subtree, then its right subtree — the order you'd get by calling out each node the instant you reach it.

This is the order that reflects a top-down, parent-before-children reading of the tree, useful whenever you need to reconstruct or copy a tree's structure from its root outward.

An empty tree simply yields an empty list, with no node to visit first.

EX 01

root = []

→ []

EMPTY TREE

EX 02

root = [1]

→ [1]

SINGLE NODE

EX 03

root = [1, null, 2, null, 3]

→ [1, 2, 3]

RIGHT-SKEWED CHAIN

the tree can hold anywhere from zero to a few thousand nodes
node values can be negative, zero, or positive
the output order is node, left subtree, right subtree — no other ordering counts

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Every node reports before either of its children do. What's the simplest way to make 'report on arrival' happen automatically?

HINT 2 THE STRUCTURE

Recursion again mirrors the definition: record the node, recurse left, recurse right. The only change from inorder is when you record.

HINT 3 ONE STEP FROM THE ANSWER

The same threading trick from inorder works here too — just record the node the instant its thread is created, before descending left, instead of when the thread is cut.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE ARRIVAL CALLPATTERN · MORRIS THREADINGroot = [4, 2, 6, 1, 3, 5, 7]

STEP 1

Preorder means node, left, right — record the instant you arrive. Morris threading still gets O(1) space: start at the root, value 4.

STEP 1 / 12 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/binary-tree-preorder-traversal.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        curr = root
        while curr:
            if not curr.left:
                res.append(curr.val)
                curr = curr.right
            else:
                pred = curr.left
                while pred.right and pred.right != curr:
                    pred = pred.right
                if not pred.right:
                    res.append(curr.val)  # record on arrival, before threading
                    pred.right = curr
                    curr = curr.left
                else:
                    pred.right = None  # cut the thread, already recorded
                    curr = curr.right
        return res

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 20 LN

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []

        def visit(node):
            if not node:
                return
            res.append(node.val)
            visit(node.left)
            visit(node.right)

        visit(root)
        return res

TIME O(N)SPACE O(N)PYTHON · TRAINING PACE · 13 LN

class Solution {
    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;
            } else {
                TreeNode pred = curr.left;
                while (pred.right != null && pred.right != curr) {
                    pred = pred.right;
                }
                if (pred.right == null) {
                    res.add(curr.val);
                    pred.right = curr;
                    curr = curr.left;
                } else {
                    pred.right = null;
                    curr = curr.right;
                }
            }
        }
        return res;
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 26 LN

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        visit(root, res);
        return res;
    }

    private void visit(TreeNode node, List<Integer> res) {
        if (node == null) {
            return;
        }
        res.add(node.val);
        visit(node.left, res);
        visit(node.right, res);
    }
}

TIME O(N)SPACE O(N)JAVA · TRAINING PACE · 16 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED