Module 17 · Binary Trees: Recursive DFS and Structural Contracts

165. Recursive Postorder Traversal

Bridge · Download this solution · All solutions and shared helpers

Problem

Return a binary tree's values in recursive postorder: left subtree, right subtree, root. Empty input returns []. Visit each node occurrence exactly once and leave all links intact.

Examples

Example 1

postorder(build_tree([1,2,3,4]))
=> [4, 2, 3, 1]

Each parent follows its complete child subtrees.

Example 2

postorder(None)
=> []

No frame has a value to emit.

Example 3

postorder(build_tree([7]))
=> [7]

The leaf emits after its two empty child calls.

Reveal the worked solution and reasoning

Why this mechanism works

Postorder delays the current node's work until both child calls have completed. It is the natural order for computing a parent summary from child summaries, as the depth and diameter problems demonstrate. Here the completed work is simply appending the parent value.

State and boundaries

visit(node) appends a subtree's entire postorder. A frame emits its value only after both delegated traversals return.

Protocol

Ignore None.
Visit left.
Visit right.
Append the current value.

Visualization

    1
   / \
  2   3
postorder: finish 2 -> finish 3 -> emit 1

Python implementation

from structures import build_tree

def postorder(root):
    output = []
    def visit(node):
        if node is None:
            return
        visit(node.left)
        visit(node.right)
        output.append(node.val)
    visit(root)
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

postorder(build_tree([1,2,3,4]))

L4 postorder: output = []
root=N1(val=1,left=N2,right=N3); output=[]

L6 visit: if node is None:
node=N1(val=1,left=N2,right=N3); output=[]

L6 visit: if node is None:
node=N2(val=2,left=N4,right=None); output=[]

L6 visit: if node is None:
node=N4(val=4,left=None,right=None); output=[]

L6 visit: if node is None:
node=None; output=[]

L6 visit: if node is None:
node=None; output=[]

L10 visit: output.append(node.val)
node=N4(val=4,left=None,right=None); output=[4]

L8 visit: visit(node.left)
node=N2(val=2,left=N4,right=None); output=[4]

... 6 intermediate state changes omitted ...

L10 visit: output.append(node.val)
node=N3(val=3,left=None,right=None); output=[4, 2, 3]

L9 visit: visit(node.right)
node=N1(val=1,left=N2,right=N3); output=[4, 2, 3]

L10 visit: output.append(node.val)
node=N1(val=1,left=N2,right=N3); output=[4, 2, 3, 1]

L11 postorder: visit(root)
root=N1(val=1,left=N2,right=N3); output=[4, 2, 3, 1]

Result: [4, 2, 3, 1]. Each parent follows its complete child subtrees.

postorder(None)

L4 postorder: output = []
root=None; output=[]

L6 visit: if node is None:
node=None; output=[]

Result: []. No frame has a value to emit.

Why the solution is correct

Empty subtrees append nothing. Correct left and right child sequences followed by the parent value give exactly left-right-root order. Every node is appended once in its own frame, and finite descent ends at missing children.

Time and space

O(n) time, O(n) output space and O(h) recursive stack space.

Common mistakes

Appending between child calls produces inorder. In an iterative version, merely pushing children without remembering whether the parent is ready can emit it too early.

Reasoning card

State: visit(node) appends a subtree's entire postorder. A frame emits its value only after both delegated traversals return.

Invariant: A parent is processed after its full subtree.

Decision to rehearse: Combine or emit only after both children are solved.

Finish: Append the current value

Transfer exercise

Use stack entries (node,expanded) to implement postorder without recursive calls.