DSA Tracker

Visualize

Binary Tree Postorder Traversal

Left, right, then self

time O(n)space O(h)

Postorder is bottom-up: a node may only report after BOTH of its subtrees are completely done, so leaves go first and the root goes last. Watch the call stack — every frame waits for the frames above it before it appends its own value.

Details

Animated on: Return the postorder traversal of the tree [1, 2, 3, 4, 5, null, 6] — expected [4,5,2,6,3,1].

Problem:Binary Tree Postorder TraversalEasy

Left, right, then self

step 1 / 9

4
2
5
1
3
6

Call stack

postorder(1)

Enter postorder(1). Its value is NOT appended yet: postorder means both subtrees (2 and 3) must be completely finished first, so this frame parks on the stack and recurses left.

Pseudocode
1FUNCTION postorder(node, out):
2  IF node = null:
3    RETURN
4  postorder(node.left, out)
5  postorder(node.right, out)
6  APPEND node.val TO out
7  RETURN out

← / → step · space play · Home restart

Every step in words

Show all 9 steps
  1. Enter postorder(1). Its value is NOT appended yet: postorder means both subtrees (2 and 3) must be completely finished first, so this frame parks on the stack and recurses left.
  2. Enter postorder(2). Its value is NOT appended yet: postorder means both subtrees (4 and 5) must be completely finished first, so this frame parks on the stack and recurses left.
  3. postorder(4) is a leaf: both child calls hit null and return immediately, so 4 is appended as element #1 — out is now [4]. Its frame pops and control returns to postorder(2).
  4. postorder(5) is a leaf: both child calls hit null and return immediately, so 5 is appended as element #2 — out is now [4, 5]. Its frame pops and control returns to postorder(2).
  5. Both subtrees of 2 have reported, so 2 finally appends itself as #3: out is [4, 5, 2]. A parent always lands AFTER everything beneath it — that is the whole definition of postorder. Frame pops back to postorder(1).
  6. Enter postorder(3). Its left child is null, so that call returns at once with nothing to add; the only child to finish is 6. Node 3 itself still has to wait — out is [4, 5, 2] and stays that way until 6 is done.
  7. postorder(6) is a leaf: both child calls hit null and return immediately, so 6 is appended as element #4 — out is now [4, 5, 2, 6]. Its frame pops and control returns to postorder(3).
  8. Both subtrees of 3 have reported, so 3 finally appends itself as #5: out is [4, 5, 2, 6, 3]. A parent always lands AFTER everything beneath it — that is the whole definition of postorder. Frame pops back to postorder(1).
  9. The root 1 is the very last node to append (#6) because nothing can finish before its children do. The stack is empty and out is [4, 5, 2, 6, 3, 1].

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Binary Tree Postorder Traversal in the editorAll Binary Trees problemsBack to roadmap