LeetCode 145 · Trees · DFS

Binary Tree Postorder Traversal, explained with a picture

Packing up: children before parents.

Trees · DFS
▶ Watch it step by step

The problem

Return a binary tree’s values in postorder: left subtree, right subtree, then the node.

Input:  [1, 2, 3, 4, 5, null, 6]
Output: [4, 5, 2, 6, 3, 1]

Picture it

Picture packing up a house of folders: you can only close a box after both boxes inside it are packed. So children are always written before their parent, and the root comes last.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Postorder DFS. O(n).

Python solution

def postorder(root):
    out = []
    def walk(node):
        if not node:
            return
        walk(node.left)
        walk(node.right)
        out.append(node.val)
    walk(root)
    return out

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.