Return the values of the tree in post-order: left subtree, then right subtree, then the node itself.
postOrder(root)
Input format: level-order with x for missing children. Output values
space-separated.
1 2 3 4 5 // → 4 5 2 3 1
1 // → 1
(empty) // → (empty)
A traversal order is a rule for when to "visit" a node relative to its subtrees. Post-order's rule: fully explore left, fully explore right, then record the node itself. The name says it — the node is recorded post, after everything beneath it.
"Fully explore a subtree" is itself just a post-order traversal of that subtree. For any node: recursively traverse left in post-order, then right in post-order, then append this node's value last. A missing node contributes nothing — the base case.
Concretely: the result for any subtree is the left subtree's post-order, then the right subtree's post-order, then this node's value.
Unlike pre-order (node, left, right) or in-order (left, node, right), post-order guarantees that by the time you record a node, everything in both its subtrees is already recorded. That's why post-order fits problems like deleting a tree bottom-up, or evaluating an expression tree, where a node's own result depends on its children's results being finished first.
Each node contributes exactly one value and is visited once — O(n) time. The output holds one entry per node — O(n) space, plus O(h) for the recursion stack.
def post_order(root):
if root is None:
return []
return post_order(root.left) + post_order(root.right) + [root.val]
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.