Binary Tree Inorder Traversal

EASY✓ CHIP-TIMEDLC #94 — FULL STATEMENT ↗

The drill: Walk a binary tree left, node, right and list every value in that order — the sequence a binary search tree hands back already sorted.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A binary tree arrives, and the task is to list out every value it holds by walking left subtree, then the current node, then right subtree — applied recursively at every node.

For a binary search tree specifically, walking in this order happens to produce the values in fully sorted ascending order, which is what makes this traversal order worth knowing by name.

An empty tree simply produces an empty list; there's no node to report and no special case to handle beyond that.

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 left subtree, node, right subtree — no other ordering counts

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Left, then this node, then right — the same rule at every node. What mechanism naturally finishes everything nested before moving on?

HINT 2 THE STRUCTURE

Recursion mirrors the definition exactly: fully walk the left subtree, record the node, fully walk the right subtree. That's the whole algorithm.

HINT 3 ONE STEP FROM THE ANSWER

For constant space, thread a temporary link from the leftmost descendant back up to the current node, walk down it, then cut the thread on the way through — no stack needed.

COACH'S BOARD — THE PATTERN, STEP BY STEP

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

STEP 1

Inorder means left, node, right — Morris threading does it with zero extra memory by temporarily wiring the tree itself as a stack substitute. Start at the root, value 4.

STEP 1 / 12 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

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

LANG ▸

PACE ▸

class Solution:
    def inorderTraversal(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:
                    pred.right = curr  # thread back to curr
                    curr = curr.left
                else:
                    pred.right = None  # cut the thread, we're done with it
                    res.append(curr.val)
                    curr = curr.right
        return res

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

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

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

        visit(root)
        return res

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

class Solution {
    public List<Integer> inorderTraversal(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) {
                    pred.right = curr;
                    curr = curr.left;
                } else {
                    pred.right = null;
                    res.add(curr.val);
                    curr = curr.right;
                }
            }
        }
        return res;
    }
}

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

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

    private void visit(TreeNode node, List<Integer> res) {
        if (node == null) {
            return;
        }
        visit(node.left, res);
        res.add(node.val);
        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