Binary Tree Postorder Traversal

EASY✓ CHIP-TIMEDLC #145 — FULL STATEMENT ↗

The drill: Walk a binary tree left, right, node and list every value in that order — every node waits to report until both of its children already have.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A binary tree arrives, and the task is to list its values by fully visiting the left subtree, then fully visiting the right subtree, and only then recording the current node — every node reports last, after both of its children already have.

This bottom-up order matters whenever children need to be processed before their parent, such as safely deleting a tree or evaluating an expression tree from the leaves inward.

An empty tree produces an empty list, since there's nothing beneath it to finish first.

EX 01

root = []

→ []

EMPTY TREE

EX 02

root = [1]

→ [1]

SINGLE NODE

EX 03

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

→ [3, 2, 1]

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

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Left, then right, then this node — the node reports last, once both children are already accounted for.

HINT 2 THE STRUCTURE

Recursion handles it directly: finish the left subtree, finish the right subtree, then record the node. It's the mirror image of preorder.

HINT 3 ONE STEP FROM THE ANSWER

For constant space, wrap the root under a dummy parent so it gets threaded too; every time a thread is cut, that closes out a whole left-boundary segment — read it off in reverse and append it.

COACH'S BOARD — THE PATTERN, STEP BY STEP

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

STEP 1

Postorder means left, right, node — record last. Morris threading conceptually hangs the whole tree under an imaginary dummy parent so even the root gets threaded; each closed boundary is read off in reverse.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

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

LANG ▸

PACE ▸

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        dummy = TreeNode(0)
        dummy.left = root
        curr = dummy
        res = []

        def reverse(node):
            prev = None
            while node:
                nxt = node.right
                node.right = prev
                prev = node
                node = nxt
            return prev

        def add_reversed(start, end):
            head = reverse(start)
            node = head
            while node:
                res.append(node.val)
                node = node.right
            reverse(head)  # restore original wiring

        while curr:
            if not curr.left:
                curr = curr.right
            else:
                pred = curr.left
                while pred.right and pred.right != curr:
                    pred = pred.right
                if not pred.right:
                    pred.right = curr
                    curr = curr.left
                else:
                    pred.right = None
                    add_reversed(curr.left, pred)
                    curr = curr.right
        return res

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

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

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

        visit(root)
        return res

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

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        TreeNode dummy = new TreeNode(0);
        dummy.left = root;
        TreeNode curr = dummy;
        List<Integer> res = new ArrayList<>();
        while (curr != null) {
            if (curr.left == null) {
                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;
                    addReversed(curr.left, pred, res);
                    curr = curr.right;
                }
            }
        }
        return res;
    }

    private TreeNode reverse(TreeNode node) {
        TreeNode prev = null;
        while (node != null) {
            TreeNode next = node.right;
            node.right = prev;
            prev = node;
            node = next;
        }
        return prev;
    }

    private void addReversed(TreeNode start, TreeNode end, List<Integer> res) {
        TreeNode head = reverse(start);
        for (TreeNode n = head; n != null; n = n.right) {
            res.add(n.val);
        }
        reverse(head);
    }
}

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

class Solution {
    public List<Integer> postorderTraversal(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);
        visit(node.right, res);
        res.add(node.val);
    }
}

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