Reference: LeetCode
Difficulty: Hard

Problem

Given a binary tree, return the postorder traversal of its nodes’ values.

Example:

Follow up: Recursive solution is trivial, could you do it iteratively?

Analysis

Recursion

Time: $O(N)$
Space: $O(h)$

Note: Another way to use recursion is related to functional programming.

Iteration (preorder-like)

Original postorder traversal is difficult to be simulated with stack. We can apply reversed-postorder traversal.

We can compare postorder and reversed-postorder traversals.

In the reversed-postorder traversal, we can see that this form of code is exactly like the preorder traversal. So, we can use the iteration code in preorder traversal.

Iteration Code:

Time: $O(N)$
Space: $O(h)$

Iteration (inorder-like)

Like the inorder traversal, we go down to the left of the tree. But this time, we push a node p‘s right child to the stack if it is not null before pushing its left child. This actually means that in the future before visiting the node p, we would visit its right child first.

“while” version:

“if” version:

Time: $O(N)$
Space: $O(h)$

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.