Postorder traversal

Both subtrees first, then the node. Children are always finished before their parent.

Time O(n)Space O(h)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

A node is recorded only after everything below it is done. The root is always last.

Code

C++PythonC#

void postorder(TreeNode* node, vector<int>& result) {
    if (!node) return;
    postorder(node->left, result);
    postorder(node->right, result);
    result.push_back(node->val);
}

def postorder(node: TreeNode | None, result: list[int]) -> None:
    if node is None: return
    postorder(node.left, result)
    postorder(node.right, result)
    result.append(node.val)

public static void Postorder(TreeNode node, List<int> result) {
    if (node == null) return;
    Postorder(node.left, result);
    Postorder(node.right, result);
    result.Add(node.val);
}

Tips

Use it whenever a parent needs answers from its children first: tree height, subtree sums, deleting a tree, evaluating an expression tree.

In the .NET library

Disposing a tree of owned resources is postorder: dispose the children, then the parent.